松江手机网站开发,微信小程序 网站建设,文化传媒 网站设计,互联网设计是做什么的正题
洛谷评测记录:https://www.luogu.org/recordnew/lists?uid52918pidUVA1328 POJ链接:http://poj.org/problem?id1961 题目大意
求一个字符串每个前缀的最短循环循环次数。 解题思路
计算next数组#xff0c;然后直接计算循环节#xff1a; 详见:POJ2752-Seek…正题
洛谷评测记录:https://www.luogu.org/recordnew/lists?uid52918pidUVA1328 POJ链接:http://poj.org/problem?id1961 题目大意
求一个字符串每个前缀的最短循环循环次数。 解题思路
计算next数组然后直接计算循环节 详见:POJ2752-Seek the Name, Seek the Fame【KMP】 code
#includecstdio
using namespace std;
int n,fail[1000001],k;
char s[1000001];
int main()
{while(true){k;scanf(%d,n);if(n0) return 0;scanf(%s,s);for(int i1,j0;in;i){while(js[i]!s[j])jfail[j];j(s[i]s[j]);fail[i1]j;}//构建失败指针printf(Test case #%d\n,k);for(int i2;in;i){if(i/(i-fail[i])1!(i%(i-fail[i]))) printf(%d %d\n,i,i/(i-fail[i]));//输出答案}printf(\n);}
}
