poj 2406 power strings

　　题意：给一个字符串，求长度最短的循环节。

　　题解：很经典的KMP的next数组的应用；因为next数组代表模板串的最大公共前后缀，因此如果该字符串有循环节的话，那么从下标 next[len-1] 到 len-1 的这一段子串就代表了最短的循环节（不怎么明白的话可以求几个诸如abcabc、ababab 字符串的next数组出来研究下）。详见代码：

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include <set>
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 const int inf=0x3f3f3f3f;
13 const double PI=acos(-1.0);
14 const double EPS=1e-8;
15 using namespace std;
16 typedef long long ll;
17 typedef pair<int,int> P;
18 
19 char str[1000005];
20 int next[1000005];
21 void makeNext()
22 {
23     int q,k;
24     int m=strlen(str);
25     next[0]=0;
26     k=0;
27     for(q=1; q)
28     {
29         while(k>0&&str[q]!=str[k]) k=next[k-1];
30         if(str[k]==str[q]) k++;
31         next[q]=k;
32     }
33     //for(int i=0;i<=m;i++) printf("%d ",next[i]);
34 }
35 bool judge(int n)
36 {
37     int len=strlen(str);
38     if(len%n!=0) return false;
39     int cnt=len/n;
40     int t=0;
41     while(t<len)
42     {
43         for(int i=0,j=t;i)
44             if(str[i]!=str[j]) return false;
45         t+=cnt;
46     }
47     return true;
48 }
49 //
50 int main()
51 {
52     //freopen("test.txt","r",stdin);
53     while(scanf("%s",str)!=EOF)
54     {
55         int len=strlen(str);
56         if(len==1&&str[0]=='.') break;
57         makeNext();
58         //
59         if((len-next[len-1])&&len%(len-next[len-1])==0) //len-next[len-1]得到一个循环节的长度
60             printf("%d\n",len/(len-next[len-1]));
61         else 
62             printf("1\n");
63         /*
64         
65         一开始的蠢做法=_=...
66         int len=strlen(str);
67         len--;
68         int ans=1;
69         while(next[len]) ans++,len=next[len]-1;//得出有多少个循环节
70         if(judge(ans)) printf("%d\n",ans); //judge()判断长度为len/ans的循环节是否可行
71         else printf("1\n");
72         */
73     }
74     return 0;
75 }

字符串

poj 2406 power strings

相关

js 正则匹配两个字符串之间，某个字符串之前（之后）的内容

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之参数化函数助手：__Random string（译：瑞德.丝锥）：随机字符串

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

python基本数据类型；关于字符串格式化的补充

Java基础-02 字符串(汉字)与16进制字符串转换(无乱码)

C语言判断给定的字符串是否为合法的ip地址的代码-C-J

把字符串a复制到字符串b，利用指针

javascript模板字符串（反引号）

标签