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;
}
上一篇:封装 vue 组件的过程


下一篇:Ext.Window 的常见属性