成都好的网站设计公司,郑州网站微信微博维护,做一个属于自己的网站,帮别人做钓鱼网站一开始以为这道题是后缀数组#xff0c;想了好久没想明白怎么做#xff0c;后来发现暴力枚举起点#xff0c;进行KMP就好了。
枚举起点以后#xff0c;构建fail数组。
遍历fail数组#xff0c;如果串s[l,r]是由串s[s,t]重复k次得到的#xff0c;那么fail数组的样子一定…一开始以为这道题是后缀数组想了好久没想明白怎么做后来发现暴力枚举起点进行KMP就好了。
枚举起点以后构建fail数组。
遍历fail数组如果串s[l,r]是由串s[s,t]重复k次得到的那么fail数组的样子一定如下
index: [l] [l1] [l2] ....[t] [t1] [t2]....[r] fail: [0] [*] [*] ...[*] [1] [2] [3] ....[r-t]
并且(r-l1)一定是(t-s1)的倍数。
len r-l1
如果len ans[k]记把ans数组k的位置更新成len。
这样的话我们在输出答案的时候要输出重复t次的最长串长度那么答案一定是ans[t],ans[2t]...ans[kt]里面的最大值
因为重复2t次也可以看作是重复t次相邻的2个合成1个来看。
时间复杂度
O(n*nnnlogn)O(n2) #include bits/stdc.h
using namespace std;
#define MAXN 2000001
const int maxn 1005;
char str[maxn];
char *s;
int fail[maxn];
int ans[maxn];
void make_fail()
{for (int i 1, j 0; s[i]; i){while (j s[i] ! s[j])j fail[j - 1];if (s[i] s[j])fail[i] j;else fail[i] 0;}
}
int cas 0;
void solve(){memset(ans,0,sizeof(ans));int len strlen(str);int pre -1;for(int i 0;i len;i){s stri;make_fail();for(int j 0;s[j];j){if(fail[j] pre 1){pre;if(pre 1 (j1)%(j1-pre) 0){ans[(j1)/(j1-pre)] max(ans[(j1)/(j1-pre)],j1);}}else if(fail[j] pre){pre 0;}}}/*for(int i 0;i len;i){coutans[i]endl;}*/printf(Case #%d: %d,cas,len);for(int i 2;i len;i){int pt 0;for(int j i;j len;j i){pt max(pt,ans[j]);}printf( %d,pt);}puts();
}
int main(){int T 1;cinT;while(T--){cinstr;solve();}return 0;
}
