首页 > 代码库 > POJ2406 KMP算法
POJ2406 KMP算法
POJ2406
问题重述：给定字符串s0，记连续的k个s前后相连组成的s0s0...s0为s0^k。输入字符串S，求最大的k，使得S = s0^k.
问题分析：
1.采用kmp算法求出前缀函数 prefix[i] (i = 1,2,... n, n = length(S)).
2.假如n - prefix[n]能够整除n， 则S能表示为k = n / (n - prefix[n])个连续s0，且k此时取到最大值
3.否则， S不能表示为连续的s0的形式， k = 1。
AC代码：
1 //Memory: 5680K Time: 313MS 2 #include <iostream> 3 #include <cstring> 4 #include <string> 5 6 using namespace std; 7 8 const int maxn = 1000010; 9 10 int prefix[maxn];11 string s;12 13 void init()14 {15 int l = s.size();16 memset(prefix, 0, sizeof(prefix));17 int k = 0;18 for (int i = 2; i <= l; i++) {19 while (k > 0 && s[k] != s[i - 1])20 k = prefix[k];21 if (s[k] == s[i - 1])22 k++;23 prefix[i] = k;24 }25 }26 27 int main()28 {29 while (cin >> s && s != ".") {30 init();31 int l = s.size();32 33 if ( prefix[l] != 0 && l % (l - prefix[l]) == 0) 34 cout << l / (l - prefix[l]) << endl;35 else36 cout << "1" << endl;37 }38 return 0;39 }
POJ2406 KMP算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。