字符串中连续出现最多的子串 & 字符串中最长反复子串
字符串中连续出现最多的子串 & 字符串中最长反复子串，这两个问题都能够用后缀数组来表示，至于后缀数组能够參考编程珠玑P156；后缀数组就是定义一个数组指针，分别指向字符串中的相应位置，例如以下：
a b c a b c a b c d e .substr[0]
b c a b c a b c d e ....substr[1]
c a b c a b c d e .......substr[2]
a b c a b c d e ..........substr[3]
b c a b c d e .............substr[4]
c a b c d e ...............substr[5]
a b c d e .................substr[6]
b c d e ...................substr[7]
c d e .....................substr[8]
d e ........................substr[9]
e ..........................substr[10]
上面的 substr 就是abcabcabcde的后缀数组；
一、字符串中连续出现最多的子串
针对这个问题能够使用后缀数组的思想，能够看到，子串连续出现，则满足 substr[0].substr(i, j - i) = substr[j].substr(0, j - i)。知道了这一点程序就好编写了，下面是C++代码：
<span style="font-size:18px;">string MaxTimesOfContinue(string str)
{
int len = str.length();
int maxCount = 0;
string longest = "";
for (int i = 0; i < len; ++i)
{
for (int j = i + 1; j < len; ++j)
{
if (str.substr(i, j - i) == str.substr(j, j - i))
{
int offset = j - i;
int count = 2;
for (int k = j + offset; j <= len; k += offset)
{
if (str.substr(i, offset) == str.substr(k, offset))
++count;
else
break;
}
if (count > maxCount)
{
maxCount = count;
longest = str.substr(i, offset);
}
}
}
}
return longest;
}</span>
二、字符串中最长反复子串
这个问题相同能够用后缀数组的思想来做，当然開始肯定想到的是暴力法，即求全部反复子串的长度，之后选择一个最长的就可以。
int Comlen(char *str1, char *str2)
{
int i = 0;
while(*str2 && (*str1++ == *str2++))
++i;
return i;
} int MaxLength(char *str)
{
if(str == NULL)
return 0;
int maxLen = 0;
int n = strlen(str);
int maxi, maxj;
for (int i = 0; i < n; ++i)
{
for(int j = i + 1; j < n; ++j)
{
int thisLen = 0;
if ((thisLen = Comlen(&str[i], &str[j])) > maxLen)
{
maxLen = thisLen;
maxi = i;
maxj = j;
}
}
}
return maxLen;
}
若是使用后缀数组的方法能够：
对于字符串 banana，其后缀数组为
a[0]:banana
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a
将后缀数组按字典排序
a[0]:a
a[1]:ana
a[2]:anana
a[3]:banana
a[4]:na
a[5]:nana
之后比較相邻两个子串就可以：
int Comlen(char *str1, char *str2)
{
int i = 0;
while(*str2 && (*str1++ == *str2++))
++i;
return i;
}
int Pstrcmp(const void *a, const void *b)
{
return strcmp(*(char**)a, *(char**)b);
}
//char *a[11];
int MaxLength(char *str)
{
if(str == NULL)
return 0;
int maxLen = 0;
int len = strlen(str);
char **a = new char *[len + 1];
for (int i = 0; i < len ; ++i)
a[i] = &str[i];
qsort(a, len , sizeof(char *), Pstrcmp);
for (int i = 0; i < len - 1; ++i)
if(Comlen(a[i], a[i+1]) > maxLen)
maxLen = Comlen(a[i], a[i+1]);
return maxLen;
}