首页 > 代码库 > POJ1961 KMP算法
POJ1961 KMP算法
POJ1961
问题重述:
输入一个长度为l的字符串S,求所有S的由字串重复排列而成的前缀,并输出前缀的长度以及该前缀的最大重复度。
AC代码:
1 //Memory: 5700K Time: 641MS 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 int n;30 int case_num = 1;31 while (cin >> n && n) {32 cin >> s;33 init();34 int l = s.size();35 cout << "Test case #" << case_num++ << endl;36 for (int k = 1; k <= l; k++) {37 if ( prefix[k] != 0 && k % (k - prefix[k]) == 0) {38 cout << k << " " << k / (k - prefix[k]) << endl;39 }40 }41 cout << endl;42 }43 return 0;44 }
POJ1961 KMP算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。