首页 > 代码库 > POJ 3450 Corporate Identity KMP题解
POJ 3450 Corporate Identity KMP题解
本题要求求一组字符串的最长公共子串,其实是灵活运用KMP快速求最长前缀。
注意肯爹的题意:要求按照字典顺序输出。
还有要提醒的就是:有人也是用KMP来解这道题,但是很多人都把KMP当成暴力法来用了,没有真正处理好细节,发挥KMP的作用。而通常这些人都大喊什么暴力法可以解决本题,没错,的确暴力法是可以解决本题的,本题的数据不大,但是请不要把KMP挂上去,然后写成暴力法了,那样会误导多少后来人啊。
建议可以主要参考我的getLongestPre这个函数,看看是如何计算最长前缀的。
怎么判断你是否把本题的KMP法写成暴力法了?
简单看看你的运行速度吧,我的下面的程序运行起来是79ms(每次运行也许有一点点差别),如果你搞出KMP运行时间300ms,甚至搞得更加高了,看到号称使用KMP搞出700多ms运行时间的,囧,那么说明你还不会KMP,你挂了个KMP外壳,写成了暴力法了。
#include <stdio.h> #include <string.h> const int MAX_N = 4001; const int MAX_CHS = 201; const int ARR_SIZE = 26; int N; char res[MAX_CHS], dict[MAX_N][MAX_CHS]; short next[MAX_CHS]; inline int min(int a, int b) { return a < b ? a : b; } inline int max(int a, int b) { return a > b ? a : b; } void getNext(char *chs, int len) { memset(next, 0, sizeof(short)*len); for (int i = 1, j = 0; i < len; ) { if (chs[i] == chs[j]) next[i++] = ++j; else if (j > 0) j = next[j-1]; else i++; } } int getLogestPre(char *chs, int len) { getNext(chs, len); for (int i = 1; i < N; i++) { char *p = dict[i]; int j = 0, tmp = 0; for (; *p && j < len; ) { if (*p == chs[j]) { p++, j++; tmp = max(tmp, j); } else if (j > 0) j = next[j-1]; else p++; } len = tmp; } return len; } int main() { while (scanf("%d", &N) && N) { getchar(); // don't forget to get rid of '\' for (int i = 0; i < N; i++) { gets(dict[i]); } int len = strlen(dict[0]), ans = 0, pos = 0; for (int i = 0; i < len; i++) { int tmp = getLogestPre(dict[0]+i, len-i); if (tmp >= ans) { if (tmp > ans) { ans = tmp; pos = i; } else { bool smaller = true; for (int t = 0; t < ans; t++) { if (dict[0][pos+t] > dict[0][i+t]) break; else if (dict[0][pos+t] < dict[0][i+t]) { smaller = false; break; } } if (smaller) pos = i; } } } if (ans) { for (int i = 0; i < ans; i++) { putchar(dict[0][pos+i]); } putchar('\n'); } else puts("IDENTITY LOST"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。