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

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

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

LCP数组是最长公共前缀数组，其中每个元素都记录了排名相邻的两个后缀的最长公共前缀长度。例如，在后缀数组为5的情况下，LCP数组为2。利用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数组的概念。通过本文的介绍，相信大家已经对于这种求解方法有了更深入的了解。

相似文章
• C++变量初始化语法详解
  C++是一门面向对象的编程语言，变量初始化是其基本语法之一。C++变量初始化语法可以帮助程序员在定义变量时为其赋初值，以提高程序的可读性和性能。
  
  
• 《数据结构与算法c++版第三版》答案解析
  《数据结构与算法c++版第三版》是一本经典的教材，涵盖了计算机科学领域中的基础数据结构和算法的内容。旨在帮助读者更好地理解和运用数据结构与算法。
  
  
• C++中的左移运算符（<<）
  C++是一种面向对象的编程语言，它被广泛应用于许多应用程序和系统开发中。在C++中，左移运算符（<<）是一种位运算符，它被用来将某个数向左移动指定的位数。
  
  
• 如何在C++中使用多线程进行面试？
  在C++中使用多线程进行面试已经成为了很多技术公司的常规操作。如果你想在面试中表现出色，那么你必须要掌握如何在C++中使用多线程，以便能够解决一些常见的并发问题和算法题。
  
  
• 如何在C++中编写求平均数的程序？
  求平均数是C++编程中最基础的一个问题，下面将介绍在C++中如何编写求平均数的程序。
  
  
• C++ 环形缓冲区
  C++
  
  
• C++的近似值：使用算法计算小数的近似值
  C++是一种常用的编程语言，它有着广泛的应用。在C++中，我们可以使用算法来计算小数的近似值，在科学计算、金融、游戏等领域具有重要的应用。
  
  
• C++强制类型转换：Int转Char
  在C++编程中，类型转换是一个常见的操作，有时候可能需要将一个整数转换为字符类型。这个转换过程需要使用强制类型转换的方法。
  
  
• C++任意输入：实现用户输入任意数据的程序设计
  在C++编程中，我们通常需要接收来自用户的输入，以便程序能够根据用户的要求做出相应的处理。而有时候用户需要输入的数据类型和数量并不确定，这时候我们就需要实现一个能够接收任意数据的程序设计。
  
  
• C++字符串截断操作
  在C++中，经常会遇到需要截断字符串的情况。字符串截断操作指的是从一个字符串中取出一部分子串。本文将介绍C++中的字符串截断操作。
  
  
• 如何使用C++中的自定义标识符
  在C++编程中，标识符是用于标识变量、函数、类、结构体及其他用户自定义标识符的名称。标识符可以由字母、数字和下划线组成，但必须以字母或下划线开头。
  
  
• C++实现ASCII码转换
  ASCII码是计算机中最基本的字符编码表示方式，每个字符都有一个对应的ASCII码值。在C++编程中，有时需要将字符串、字符等转换为ASCII码，或者将ASCII码转换为对应的字符。本文将介绍C++中如何实现ASCII码转换。
  
  
• 学习：使用数组基础玩转C++石头剪刀布游戏
  石头剪刀布游戏是一款简单又有趣的游戏，它可以让我们了解如何使用数组基础来实现C++的编程。这篇文章将带领你学习如何使用数组来实现石头剪刀布游戏。
  
  
• C++ 缩进格式：如何让代码更易读
  C++是一种常用的编程语言，编写代码时，我们除了关注代码的实现逻辑和功能外，还需要注重代码的可读性，这就需要我们采用合适的缩进格式，让代码更易读。
  
  
• 为什么C++中的case 1、2、3会出错？
  C++是一种常用的编程语言，在编写程序时，我们常常会使用到switch语句，其中包含了多个case选项。然而，在一些情况下，我们会遇到一个很奇怪的问题，即在使用case
  
  
• 如何在C++中判断一个小数的位数？
  在C++中，可以使用各种方法来判断一个小数的位数。下面介绍几种实用的方法。
  
  
• C++实现圆柱体积函数
  C++是一种强大的编程语言，其广泛的应用领域包括游戏、科学计算、嵌入式系统、人工智能等。在计算几何学中，C++也是一种很常见的编程语言，可以用来求解各种几何问题，例如计算圆柱体积等。
  
  
• C++中的嵌套类示例
  在C++中，嵌套类是指一个类定义在另一个类内部的情况。嵌套类可以用于实现一些高级的编程技术。在本文中，我们将会介绍一个使用嵌套类的示例。
  
  
• C++如何实现每行输出5个数？
  C++是一种面向对象的编程语言，广泛应用于计算机科学和工程领域。在我们进行一些数字计算或者输出数据的时候，经常需要每行输出一定数量的数据，以方便我们观察和计算。例如，在打印一段固定长度的整数序列或者对一个数组进行遍历时，我们往往需要按照每行
  
  
• C++中如何创建一个n行m列全为0的二维数组
  在C++中，创建一个n行m列全为0的二维数组可以通过如下代码实现：
  
  
• C++的编写：空格的使用
  C++是一种非常强大的编程语言，但在编写C++代码时，空格的使用是非常重要的。
  
  
• 「C++代码画樱花」的实现方法
  C++代码画樱花的实现方法
  
  
• C++小数的输入输出应该一致
  C++是一种广泛使用的编程语言，也是许多人入门编程的第一步。当我们在使用C++进行编程时，输入输出是非常重要的组成部分。而在输出小数的时候，输入输出应该要一致，这一点非常重要。
  
  
• 哪款C++手机编译器是较好的选择？
  如果您是一名开发人员，并且想要在手机上编写和调试C++代码，那么您需要一款C++手机编译器。毫无疑问，有许多不同的编译器可供选择，但是哪一种是较好的选择呢？在本文中，我们将讨论一些最受欢迎的选项，帮助您找到最适合自己需求的C++手机编译器。
  
  
• 修正c++字符串转换为整数的错误
  在C++中，将字符串转换为整数是一项常见的任务。通常，我们使用stoi函数来实现这个任务。但是，如果使用不恰当，可能会导致错误。本文将介绍一些常见错误，并提供修复方法。
  
  
• C++编写的钟表类
  在C++编程中，钟表类是一个常见的类。这个类用来表示时间，包括小时、分钟和秒。
  
  
• C++源程序文件编译后执行文件的后缀名是什么？
  C++源程序文件是计算机程序设计中常见的一种文件类型，它通常以.cpp或.cc作为后缀名。这些源程序文件包含了C++程序的源代码，它们可以通过编译器将代码翻译成计算机能够执行的二进制代码。
  
  
• C++构造函数重载
  C++中的构造函数可以被重载，即在同一个类中可以有多个不同的构造函数。重载的构造函数有着相同的名称，但是参数列表不同。
  
  
• C++编程：将数组逆序存放
  在C++编程中，经常需要对数组进行各种操作。其中一种常见的操作是将数组逆序存放。这个操作可以实现数组中元素顺序的翻转，使得我们能够更加方便地处理数组数据。
  
  
• C++实现九九乘法表代码
  九九乘法表是我们小学时期必须要掌握的一项数学技能，而在编程中，我们也可以用C++语言来实现它。下面就让我们一起来看看如何用C++语言实现九九乘法表的代码吧！
  
  
• Linux C++获取当前程序版本的方法
  对于Linux
  
  
• "C++ 开发安卓应用程序"
  C++是一种多用途的程序设计语言，能够用于开发多种领域的应用程序，包括桌面应用程序、网站和游戏等。近年来，越来越多的开发者开始使用C++来开发移动应用程序，特别是安卓应用程序。
  
  
• 学习C++多久才能找到工作？
  在当今这个快速发展的时代，计算机科学技术已成为了世界上最为热门的领域之一。这也使得越来越多的人选择学习计算机程序设计语言，其中最受欢迎的就是C++。然而，对于许多初学者而言，一个问题会经常困扰他们:
  
  
• 如何在C++中打换行符？
  在C++中，换行符是一个特殊的字符，表示文本换行。通常情况下，我们使用“\n”来表示换行符，这也是C++中最常用的方法。我们可以在字符串中添加“\n”，也可以使用文本输出函数，例如cout，来在输出中添加换行符。
  
  
• 如何在C++中表示ln函数
  在C++编程中，数学函数是使用特定库来表示的。其中包括许多基本常用数学函数。不过，如果你需要在C++程序中使用国际自然对数函数ln(x)，你需要了解如何表示它。
  
  
• 【对比解析】C语言与C++的区别与联系
  C语言和C++是两种流行的编程语言，都具有自己的优势和适用场景。虽然它们有相同的起源，但它们之间存在一些区别和联系。
  
  
• C++ 数组复制方法
  在C++中，数组是一组相同类型数据的集合，它们被存储在连续的内存单元中。有时候，我们需要将一个数组的值复制到另一个数组中，这对于数据处理和算法实现非常有用。在本文中，我们将介绍C++中的两种方法来复制数组。
  
  
• C++中的动态内存容器
  C++中的动态内存容器是一种方便管理动态内存的工具，它可以在运行时动态地分配和释放内存。C++中有多种动态内存容器，其中最常见的包括vector、list、deque和map等。
  
  
• C++如何定义正整数？
  在C++中，正整数可以用一些不同的数据类型来表示。下面我们来学习一些基础知识。
  
  
• 这里应该学习C语言还是C++？
  对于计算机科学专业的学生，学习编程是必不可少的一部分。而在学习编程之前，需要选择一门编程语言作为起点。对于学习C语言还是C++，很多人常常感到困惑。下面将从几个方面分析，看看应该学习C语言还是C++。
  
  
• C++如何实现两个数交换
  在编程语言中，有时我们需要交换两个变量的值，这在C++中也是很常见的操作。要实现两个数的交换，可以使用以下两种方法：
  
  
• How to change C++ to display in Chinese?
  If
  
  
• C++派生的含义是什么？
  C++是一种面向对象的编程语言，支持派生类的概念。派生是指一个类从另一个类继承了所有的数据成员和成员函数，并添加了自己特殊的功能。这意味着一个派生类可以重用基类的所有属性和方法。
  
  
• C++怎样退出程序？
  C++是一种非常流行的编程语言，其功能强大，灵活性高，可广泛应用于各种领域。在使用C++编写程序时，我们常常需要让程序在特定条件下退出，以确保程序的正常结束。那么，C++怎样退出程序呢？下面我们来详细介绍一下。
  
  
• 《C++指针头文件》
  在C++中，指针是一种非常重要的数据类型，它可以用来存储变量的地址，从而在程序中进行间接访问和操作。为了方便开发人员对指针进行操作，C++提供了一些头文件，这些头文件包含了一些专门用于指针操作的函数和类。
  
  
• C++宏变量简介
  C++宏变量是一种常用的编程工具，它允许程序员在编写代码时使用简单的记号来代替复杂的代码块或表达式。宏变量通常用在大型代码库中，用于提高代码的可读性和可维护性。在这篇文章中，我们将对C++宏变量进行简要介绍。
  
  
• C++如何比较n个数的大小
  在进行编程时，常常需要比较多个数之间的大小关系，使程序具有更高的实用价值。对于C++语言而言，比较n个数的大小通常可以采用以下几种方式来实现。
  
  
• C++ 输入 int 数组
  C++是一种非常流行的编程语言，具有广泛的应用。在C++中，我们可以使用数组来存储多个元素。输入一个int数组是一个非常常见的需求，因为很多时候我们需要从用户那里获取一些整数并将它们存储在一个数组中。
  
  
• 如何在C++中制作界面菜单
  在C++中，制作界面菜单是一项基本技巧。在本文中，我们将介绍如何使用C++的基本语法和重要库来制作一个简单的界面菜单。下面是一步一步的指南。
  
  
• C++中的引用
  引用是C++中的一种非常特殊的数据类型，它提供了一种简便的方式来访问某个变量的地址。引用允许我们创建一个指针别名，使我们能够像使用变量一样使用它来作为函数参数和返回值。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政