主页 / 问题 / 1200280
Accepted
Alrott SlimRG
Asked:2021-11-05 16:07:00 +0000 UTC2021-11-05 16:07:00 +0000 UTC

如何找到向量中子向量的最大出现的长度

  • 772

有一个向量：std::vector<char> main {'1','2','3','4','5','6','7','8','9'}
例如，有一个向量std::vector<char> sub {'3','4','5','5','6'}

如您所见，向量在第2 个sub位置进入（从零开始计数） 并且最大进入的长度为3（三个）位置（开头重合，然后）main
'3','4','5''5' != '6'

问题：
如何在代码中做到这一点？

c++

2 个回答

  1. 整个任务简化为只有两个顺序操作，在一个循环中执行：

    1. 搜索第一次出现

    2. 计算条目的长度

    这是一个带有一些注释的示例代码：

    // main.cpp

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <vector>

std::pair<std::vector<int>::const_iterator, size_t>
getBigestMatch(const std::vector<int> &vec, const std::vector<int> &sub) {
  assert(sub.empty() == false);

  // if nothing found return iterator to end and 0 len
  auto retval = std::make_pair(vec.end(), 0);

  for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
    // find first match
    iter = std::find(iter, vec.end(), sub[0]);
    if (iter == vec.end()) {
      break;
    }

    // calculate len of sequence
    int len = 1;
    for (auto found = std::next(iter), compare = std::next(sub.begin());
         found != vec.end() && compare != sub.end() && *found == *compare;
         ++found, ++compare, ++len)
      ;

    // if new sequence bigger then previous, then set it as retval
    if (len > retval.second) {
      retval = std::make_pair(iter, len);
    }
  }

  return retval;
}

int main() {
  std::vector<int> main{1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::vector<int> sub{3, 4, 5, 5, 6};

  auto found = getBigestMatch(main, sub);

  std::cout << std::distance(main.cbegin(), found.first) << " " << found.second
            << std::endl;

  return EXIT_SUCCESS;
}
    • 2
  2. Best Answer

    计算由 sub + "@" + main 组合组成的向量的 z 函数，其中分隔符 "@" 是两个输入中都不出现的字符。

    vector<int> z_function (string s) {
    int n = (int) s.length();
    vector<int> z (n);
    for (int i=1, l=0, r=0; i<n; ++i) {
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            ++z[i];
        if (i+z[i]-1 > r)
            l = i,  r = i+z[i]-1;
    }
    return z;
}

    z[i+sub.size+1]现在找到范围上的最大值i=0..main.size-1（参见指定页面上的“在字符串中搜索子字符串”部分），i 索引将指示位置，即最大值。z - 长度。

    时间是线性的O(sub.size + main.size)

    • 1

相关问题