备考首页> 数据结构> 字符串
6

问答题 6 /86

给定一个字符串,求出其最长的重复子串。

参考答案

举例： ask not what your country  can do for you ,but what you can do for your  country

最长的重复子序列：can do for you

思路：使用后缀数组解决

分析：

1、由于要求最长公共子序列，则需要 找到字符串的所有子序列 ，即通过产生字符串的后缀数组实现。

2、由于要求最长的重复子序列，则需要对所有子序列进行排序，这样可以把 相同的字符串排在一起 。

3、 比较 相邻字符串 ，找出两个子串中，相同的字符的个数。

注意，对于一个子串，一个与其重复最多的字符串肯定是紧挨着自己的两个字符串。

步骤：

1、对待处理的字符串 产生后缀数组

2、 对后缀数组排序

3、依次 检测相邻两个后缀的公共长度

4、 取出最大 公共长度 的前缀


举例： 输入字符串 banana

1、字符串产生的后缀数组：
a[0]:banana
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a

2、对后缀数组进行快速排序，以将后缀相近的（变位词）子串集中在一起

a[0]:a
a[1]:ana
a[2]:anana
a[3]:banana
a[4]:na
a[5]:nana

之后可以依次检测相邻两个后缀的公共长度并取出最大公共的前缀

代码：

  1. /*给定出一个字符串，输出最长的重复子字符串*/
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string>
  5. using namespace std;
  6. const int MaxCharNum = 5000000;
  8. bool StrCmp(char* str1,char* str2);
  9. void GenSuffixArray(char* str,char* suffixStr[]);
  10. int ComStrLen(char* str1,char* str2);
  11. void GenMaxReStr(char* str);
  13. int main()
  14. {
  15. char str[MaxCharNum];
  16. cin.getline(str,MaxCharNum);//遇到回车结束
  17. GenMaxReStr(str);
  18. system("pause");
  19. return 1;
  20. }
  22. void GenMaxReStr(char* str)
  23. {
  24. int len = strlen(str);
  25. int comReStrLen = 0;
  26. int maxLoc = 0;
  27. int maxLen = 0;
  28. char* suffixStr[MaxCharNum];
  29. GenSuffixArray(str,suffixStr);//产生后缀数组
  30. //对后缀数组进行排序
  31. sort(suffixStr,suffixStr+len,StrCmp);
  33. //统计相邻单词中相同的字符数，并输出结果
  34. for (int i = 0;i < len-1;i++ )
  35. {
  36. comReStrLen = ComStrLen(suffixStr[i],suffixStr[i+1]);
  37. if (comReStrLen > maxLen)
  38. {
  39. maxLoc = i;
  40. maxLen = comReStrLen;
  41. }
  42. }
  43. //输出结果
  44. for (int i = 0;i < maxLen;i++)
  45. {
  46. cout<<suffixStr[maxLoc][i];
  47. }
  48. cout<<endl;
  49. }
  50. /*为字符串产生其后缀数组，并存放到数组suffixStr中*/
  51. void GenSuffixArray(char* str,char* suffixStr[])
  52. {
  53. int len = strlen(str);
  54. for (int i = 0;i < len;i++)
  55. {
  56. suffixStr[i] = &str[i];
  57. }
  58. }
  59. /*返回str1和str2的共同前缀的长度*/
  60. int ComStrLen(char* str1,char* str2)
  61. {
  62. int comLen = 0;
  63. while(*str1 && *str2)
  64. {
  65. if (*str1 == *str2)
  66. {
  67. comLen++;
  68. }
  69. str1++;
  70. str2++;
  71. }
  72. return comLen;
  73. }
  75. //字符串升序排序
  76. bool StrCmp(char* str1,char* str2)
  77. {
  78. if (strcmp(str1,str2) >=0 )
  79. {
  80. return false;
  81. }
  82. return true;
  83. }

程序输入：ask not what your country can do for you,but what you can do for your country

输出：can do for you

时间复杂度分析：产生后缀数组-时间复杂度O(N)、对后缀数组排序是O(N*NlogN)，第一个N表示字符串的比较，后面NlogN使用快排排序。依次检测相邻两个后缀的公共长度-时间复杂度O(N*N)、取出最大公共长度的前缀-时间复杂度O(N)。

总的时间复杂度是O(N*NlogN)

纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号