5-4 D. DS串应用—最长重复子串

题目描述

求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。

输入

测试次数t

t个测试串

输入样例：

3
abcaefabcabc
szu0123szu
szuabcefg

输出

对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.

输出样例：

4
3
-1

思路

代码

#include <iostream>
using namespace std;int getNextMax(string s){s += " ";int len = s.length(), i=1, j=0;int next[len+1];next[1] = 0;while(i < len){if(j == 0 || s[i-1] == s[j-1]){i++;j++;next[i] = j;}else{j = next[j];}}int maxNum=1;for(int i = 1; i <= len; i++){if(next[i] > maxNum){maxNum = next[i];}}if(maxNum == 1){return -1;}else{return maxNum-1;}
}int main()
{int t;string s;cin >> t;while(t--){cin >> s;int res = getNextMax(s);cout << res << endl;}return 0;
}