C++实现求字符串的最长重复子串 |21xrx.com

C++实现求字符串的最长重复子串

2023-07-12 09:23:02 深夜i -- --

C++ 字符串最长重复子串

C++是一种流行的编程语言，广泛应用于软件开发中。在字符串处理方面，C++也具备强大的能力。其中，一个重要的应用场景是求字符串的最长重复子串。下面，我们将介绍利用C++实现求字符串最长重复子串的方法。

最长重复子串是指一个字符串在原字符串中出现至少两次的一段子串，且这段子串不能够在其它位置再次出现。例如，字符串“abcabcde”中，“abc”就是该字符串的最长重复子串。为了求解最长重复子串，我们可以利用后缀数组和LCP数组的方法。

后缀数组是一个数组，其中每个元素都记录了原字符串中以该位置开头的后缀在原字符串中的位置。例如，对于字符串“abcabcde”，其后缀数组为6。利用后缀数组，我们可以将原字符串转化为若干个后缀，并用后缀数组的索引来表示它们在原字符串中的位置。

LCP数组是最长公共前缀数组，其中每个元素都记录了排名相邻的两个后缀的最长公共前缀长度。例如，在后缀数组为7的情况下，LCP数组为3。利用LCP数组，我们可以快速地比较两个后缀的重复情况。

具体地，我们可以遍历后缀数组和LCP数组，对于相邻的两个后缀，如果它们的LCP长度超过已知的最大值，则更新最大值和对应的子串。最终，我们就可以得到原字符串中的最长重复子串了。下面是C++代码的实现：


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int n;
char s[MAXN];
int sa[MAXN], rk[MAXN], height[MAXN], tmp[MAXN];
bool cmp(int i, int j, int k) {
  return tmp[i] == tmp[j] && tmp[i+k] == tmp[j+k];
}
void build_sa() {
  for (int i = 1; i <= n; ++i) {
    rk[i] = s[i];
    sa[i] = i;
  }
  for (int k = 1; k <= n; k <<= 1) {
    sort(sa+1, sa+n+1, [&](int i, int j) { return cmp(i,j,k) ? rk[i] < rk[j] : tmp[i] < tmp[j]; });
    memcpy(tmp, rk, sizeof(rk));
    int p = 0;
    for (int i = 1; i <= n; ++i) {
      rk[sa[i]] = cmp(sa[i], sa[i-1], k) ? p : ++p;
    }
    if (p == n) break;
  }
}
void build_height() {
  for (int i = 1; i <= n; ++i) {
    rk[sa[i]] = i;
  }
  int k = 0;
  for (int i = 1; i <= n; ++i) {
    if (rk[i] == 1) continue;
    if (k) --k;
    int j = sa[rk[i]-1];
    while (i+k <= n && j+k <= n && s[i+k] == s[j+k]) ++k;
    height[rk[i]] = k;
  }
}
int main() {
  scanf("%s", s+1);
  n = strlen(s+1);
  build_sa();
  build_height();
  int ans = 0, pos = 0;
  for (int i = 2; i <= n; ++i) {
    if (height[i] > ans) {
      ans = height[i];
      pos = sa[i];
    }
  }
  printf("The longest repeated substring is '%s' with length %d.\n", s+pos, ans);
  return 0;
}

在本代码中，我们首先定义了MAXN为输入字符串的最大长度。然后，我们定义了三个数组：sa、rk和height。sa数组用于记录后缀数组，rk数组用于记录排名，height数组用于记录LCP。

例如，对于字符串“abcabcde”，它的后缀数组为{7,6,4,5,2,1,3,0}，排名rk数组为{0,5,3,1,6,4,2,7}，LCP数组为{0,1,3,0,2,3,0}。我们可以看到，rk[i]表示以位置i的后缀在排名中的位置，height[i]表示排名为rk[i]和rk[i-1]的两个后缀的LCP长度。

build_sa函数用于构建后缀数组，它采用倍增法排序。具体来说，我们在每次排序时，首先按照前k个字符排序，然后按照前2k个字符排序，直到最后按照全部字符排序。其中，cmp函数用于判断两个后缀是否相等。

build_height函数用于构建LCP数组，它采用了Kasai算法。我们首先将后缀数组转化为rk数组，然后对于每个位置i，通过LCP的定义与rk数组和height数组来计算LCP[i]的值。

最后，我们在main函数中遍历height数组，找到最长重复子串的位置和长度。输出即可。

在本文中，我们介绍了C++实现求字符串最长重复子串的方法，其中利用了后缀数组和LCP数组的概念。通过本文的介绍，相信大家已经对于这种求解方法有了更深入的了解。

上一篇: idea打包java可执行jar包

下一篇: OpenCV C++编译教程

评论区

()

相似文章