首页 > 代码库 > POJ 2752 Seek the Name, Seek the Fame KMP题解
POJ 2752 Seek the Name, Seek the Fame KMP题解
本题是KMP的next数组的灵活运用。
具体就是看最后整个数列的最后一个字母,能有多少前缀。
理解了next数组就很容易了。
#include <stdio.h> #include <string.h> #include <vector> using std::vector; const int MAX_N = 400001; char name[MAX_N]; int next[MAX_N], len; void genNext() { for (int i = 1, j = 0; i < len; ) { if (name[i] == name[j]) next[i++] = ++j; else if (j > 0) j = next[j-1]; else i++; } } void getPreSuf(vector<int> &rs) { rs.clear(); int i = len; while (i > 0) { rs.push_back(i); i = next[i-1]; } } int main() { vector<int> rs; while (gets(name)) { len = strlen(name); memset(next, 0, sizeof(int)*len); genNext(); getPreSuf(rs); for (int i = (int)rs.size()-1; i >= 0; i--) { printf("%d ", rs[i]); } putchar('\n'); } return 0; }
要使嫌保存结果麻烦,也可以直接递归打印出来,不需要保存中间结果了:
#include <stdio.h> #include <string.h> const int MAX_N = 400001; char name[MAX_N]; int next[MAX_N], len; void genNext() { for (int i = 1, j = 0; i < len; ) { if (name[i] == name[j]) next[i++] = ++j; else if (j > 0) j = next[j-1]; else i++; } } void printPreSuf(int i) { if (i > 0) { printPreSuf(next[i-1]); printf("%d ", i); } } int main() { while (gets(name)) { len = strlen(name); memset(next, 0, sizeof(int)*len); genNext(); printPreSuf(len); putchar('\n'); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。