这个问题，需要一组字符串求最长公共子，其实灵活运用KMP高速寻求最长前缀。

请注意，意大利愿父亲：按照输出词典的顺序的规定。

另外要提醒的是：它也被用来KMP为了解决这个问题，但是很多人认为KMP使用的暴力方法，没有真正处理的细节。发挥KMP角色。而通常这些人都大喊什么暴力法能够解决本题，没错，的确暴力法是能够解决本题的，本题的数据不大，可是请不要把KMP挂上去，然后写成暴力法了。那样会误导多少后来人啊。

建议能够主要參考我的getLongestPre这个函数，看看是怎样计算最长前缀的。

怎么推断你是否把本题的KMP法写成暴力法了？

简单看看你的执行速度吧。我的以下的程序执行起来是79ms(每次执行或许有一点点区别）。假设你搞出KMP执行时间300ms，甚至搞得更加高了，看到号称使用KMP搞出700多ms执行时间的，囧，那么说明你还不会KMP，你挂了个KMP外壳，写成了暴力法了。

#include 
     
      #include 
      
       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;}