首页 > 代码库 > HDU--3746--Cyclic Nacklace【KMP】
HDU--3746--Cyclic Nacklace【KMP】
链接:http://acm.hdu.edu.cn/showproblem.php?pid=3746
题意:在一个字符串后最少加几个字符才能使这个字符串是某个串重复两次而得。
思路:借助了这篇博文的结论:传送门
结论:len-next[i]为此字符串的最小循环节(i为字符串的结尾),另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 10100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 char str[100100]; int next[100100]; void getnext(){ int i,j; i = 0, j = -1; int l = strlen(str); next[0] = -1; while(i<l){ if(j==-1||str[i]==str[j]){ i++; j++; next[i] = j; } else j = next[j]; } } int main(){ int i,j,t; scanf("%d",&t); while(t--){ scanf("%s",str); getnext(); int l = strlen(str); int x = l - next[l]; if(next[l]==0) printf("%d\n",l); else if(l%x==0) printf("0\n"); else printf("%d\n",x-l%x); } return 0; }
HDU--3746--Cyclic Nacklace【KMP】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。