最长重复子串 |
您所在的位置：网站首页 › 求串中出现的第一个最长重复子串及其位置 › 最长重复子串 |
|
思路：使用后缀数组解决 分析： 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 之后可以依次检测相邻两个后缀的公共长度并取出最大公共的前缀 #include #include #include #include //#include "Customer.h" using namespace std; int mycmp(const void *p1, const void *p2) { return strcmp(*(char**)p1, *(char**)p2); } int getLen(char *p, char *q) { int ret = 0; while ( *p && *p++ == *q++) ++ret; return ret; } //最长重复子串，后缀数组 int getMaxRepeatSubStr(string str) { char *s = new char[str.length()+1]; for (int i = 0; i < str.length(); i++) s[i] = str[i]; s[str.length()] = '\0'; int len = str.length(); char **suffix = new char*[len]; for (int i = 0; i < len; i++) suffix[i] = s + i; qsort(suffix, len, sizeof(char*), mycmp); int maxlen = 0; for (int i = 0; i < len - 1; i++) { int tmp = getLen(suffix[i], suffix[i + 1]); if (tmp>maxlen) maxlen = tmp; } delete s; delete suffix; return maxlen; } int main() { string str; while (cin >> str) { getMaxRepeatSubStr(str); } return 0; } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |