最长重复子串

刺骨的言语ヽ痛彻心扉 2022-06-17 03:16 175阅读 0赞

思路：使用后缀数组解决

分析：

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 <iostream>  
    #include <string>  
    #include <vector>
    #include <algorithm>
    //#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;
    }