DS串应用—最长重复子串

题目描述

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

输入

测试次数t

t个测试串

输出

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

输入样例1 

3 abcaefabcabc szu0123szu szuabcefg

输出样例1

4 3 -1

思路分析

这玩意其实可以用KMP去做，为什么呢，KMPNB的地方不仅仅因为它可以用了找子串，它的next值非常有用，有个子串循环定理：

定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]。

这里的next值是下标从0开始的。

但是我做这道题的时候还没有想那么多，我直接暴力解决……

我直接两个循环去找最长的子串，外循环固定子串的起始位置，内循环控制子串的终止位置，记录每次子串的长度，之后输出最长的长度。

这里的生成子串的函数substr的参数是起始位置和选取的数目，而不是起始位置和终止位置。

AC代码

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string test;
        cin >> test;
        size_t i=0;
        int maxlength=0;
        for(i=0;i<test.size()-1;i  ){
			int temp=0;
			for(size_t j=1;j<test.size()-i;j  ){
				string son=test.substr(i,j),remaining=test.substr(i j,test.size()-i-j);
				if(remaining.find(son)!=string::npos)
				temp  ;
				else break;
			}
			if(maxlength<temp)
			maxlength=temp;
		}
		if(maxlength)
		cout<<maxlength<<endl;
		else cout<<"-1"<<endl;
    }
}

int size string 测试 函数

0 人点赞