【题目来源】:https://vjudge.net/problem/HUST-1010 【题意】 给出一段字符串,问最小周期是多少。。 【思路】 KMP中next数组裸题,对于next数组,当前长度减去当前的next数值等于最小周期。 【代码】
#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<limits.h> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int mod=1e9+7; const double esp=1e-5; typedef unsigned long long ll; typedef long long LL; char s[1000000+10]; int nexts[1000000+10]; int len; void get_next() { int i,j; j=nexts[0]=-1; i=0; while(i<len) { while(-1!=j&&s[i]!=s[j]) j=nexts[j]; nexts[++i]=++j; } } int main() { while(~scanf("%s",s)) { len=strlen(s); get_next(); int ans=len-nexts[len]; printf("%d\n",ans); } }