POJ2406 kmp算法next数组-串的最小循环节/循环周期

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了POJ2406 kmp算法next数组-串的最小循环节/循环周期，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1090字，纯文字阅读大概需要2分钟。

内容图文

题目链接：http://poj.org/problem?id=2406

题目大意：问给出的字符串最多由多少个子串相乘得来的。

思路：利用next数组的含义来解。

1.一个串的最小循环节长度：len - next[len] 

2.若len%(len-next[len]) == 0, 则这个字符串的最小周期为len/(len-next[len])。一定要注意前提是 len % (len - next[len]) == 0,否则不存在循环周期。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 const int MAXN = 1000000 + 10;
 5 
 6 char s[MAXN];
 7 int s_len, next[MAXN];
 8 
 9 void get_next()
10 {
11     next[0] = -1;
12     int j = 0, k = -1;
13     s_len = strlen(s);
14     while(j < s_len)
15     {
16         if(k == -1 || s[j] == s[k])
17         {
18             j ++, k ++;
19             next[j] = k;
20         }
21         else
22             k = next[k];
23     }
24 }
25 
26 int main()
27 {
28     while(scanf("%s", s) != EOF)
29     {
30         if(strcmp(s, ".") == 0)
31             break;
32         get_next();
33         if(s_len % (s_len - next[s_len]) == 0)
34             printf("%d\n", s_len / (s_len - next[s_len]));
35         else
36             printf("1\n");
37     }
38     return 0;
39 }

POJ2406

 

 

内容总结

以上是互联网集市为您收集整理的POJ2406 kmp算法next数组-串的最小循环节/循环周期全部内容，希望文章能够帮你解决POJ2406 kmp算法next数组-串的最小循环节/循环周期所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---