题意:
求出最长公共前后缀 不能重叠 而且 这个前后缀 在串的中间也要出现一次
解析:
再明确一次 next 数组的意思: 完全匹配的最长前后缀长度
求一遍 next 然后暴力枚举就好了
- #include <iostream>
- #include <cstdio>
- #include <sstream>
- #include <cstring>
- #include <map>
- #include <cctype>
- #include <set>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #define rap(i, a, n) for(int i=a; i<=n; i++)
- #define rep(i, a, n) for(int i=a; i<n; i++)
- #define lap(i, a, n) for(int i=n; i>=a; i--)
- #define lep(i, a, n) for(int i=n; i>a; i--)
- #define rd(a) scanf("%d", &a)
- #define rlld(a) scanf("%lld", &a)
- #define rc(a) scanf("%c", &a)
- #define rs(a) scanf("%s", a)
- #define MOD 2018
- #define LL long long
- #define ULL unsigned long long
- #define Pair pair<int, int>
- #define mem(a, b) memset(a, b, sizeof(a))
- #define _ ios_base::sync_with_stdio(0),cin.tie(0)
- //freopen("1.txt", "r", stdin);
- using namespace std;
- const int maxn = 1e6+10, INF = 0x7fffffff;
- int nex[maxn];
- void get_next(char *s)
- {
- int len = strlen(s);
- int j = 0, k = -1;
- nex[0] = -1;
- while(j <len)
- {
- if(k == -1 || s[j] == s[k])
- nex[++j] = ++k;
- else
- k = nex[k];
- }
- }
- int kmp(char *s, char *t, int len1, int len2) // 串 1 串 2 串 1 的长度 串 2 的长度
- {
- int i, j = 0;
- if(len1 == 1 && len2 == 1)
- {
- if(s[0] == t[0])
- return true;
- else
- return false;
- }
- for(int i=0; i<len1; i++)
- {
- while(j> 0 && s[i] != t[j])
- j = nex[j];
- if(s[i] == t[j])
- j++;
- if(j == len2)
- return true;
- }
- }
- char s[maxn];
- char s2[maxn];
- int main()
- {
- int T;
- rd(T);
- while(T--)
- {
- rs(s);
- get_next(s);
- int len = strlen(s);
- if(!nex[len]){
- cout<<"0" <<endl;
- }
- else
- {
- int tmp = nex[len];
- while(tmp)
- {
- if(tmp*3> len) // 如果当前长度大于三倍 那么就用次长来匹配
- {
- tmp = nex[tmp];
- continue;
- }
- for(int i=0; i<tmp; i++) // 暴力取出那段子串
- s2[i] = s[i];
- if(kmp(s+tmp, s2, len - 2*tmp, tmp))
- {
- cout<< tmp <<endl;
- break;
- }
- tmp = nex[tmp];
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2729645.html