HDU 3746 Cyclic Nacklace KMP
KMP算法——
AC代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; const int N=200005; const LL II=100000000; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int next[N],len,nextval[N]; char str[N]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j<len)//len是p的长度 { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } void getnextval(const char *p) { int i = 0,j =-1; nextval[0]=-1; while(i!=len) { if(j==-1||p[i]==p[j]) { ++i;++j; if(p[i]!=p[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } } int main() { int i,j,T; cin>>T; while(T--) { scanf("%s",str); len=strlen(str); getnext(str); int min_repeat=len-next[len]; if(min_repeat==len) printf("%d\n",len); else if(len%min_repeat==0) printf("0\n"); else printf("%d\n",min_repeat-len%min_repeat); } return 0; } #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; const int N=200005; const LL II=100000000; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int next[N],len,nextval[N]; char str[N]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j<len)//len是p的长度 { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } void getnextval(const char *p) { int i = 0,j =-1; nextval[0]=-1; while(i!=len) { if(j==-1||p[i]==p[j]) { ++i;++j; if(p[i]!=p[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } } int main() { int i,j,T; cin>>T; while(T--) { scanf("%s",str); len=strlen(str); getnext(str); int min_repeat=len-next[len]; if(min_repeat==len) printf("%d\n",len); else if(len%min_repeat==0) printf("0\n"); else printf("%d\n",min_repeat-len%min_repeat); } return 0; }
补充:软件开发 , C++ ,