2971380_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int N, tmp;
struct node
{
	char str[203];
}id[4001];

int pai[203];
int lenth[203];

void pre(char p[])
{
	int k, q;

	pai[1] = 0;
	k = 0;
	for(q = 2; q <= lenth[0]; q++)
	{
		while(k>0&&p[k+1]!=p[q])
			k = pai[k];
		if(p[k+1]==p[q])
			k++;
		pai[q] = k;
	}
}

void kmp(char p[],char t[],int j,int m)
{
	int i, q;

	q = 0;
	for(i = 1; i <= lenth[j]; i++)
	{
		while(q>0&&p[q+1]!=t[i])
			q = pai[q];
		if(p[q+1]==t[i])
			q++;
		if(q > tmp)
			tmp = q;
		if(q==m)
		{
			tmp = m;
			break;
		}
	}
}

int main()
{
	int i, j;
	int max, l;
	char ans[201];

	while(scanf("%d",&N),N)
	{
		for(i = 0; i < N; i++)
		{
			scanf("%s",&id[i].str[1]);
			lenth[i] = strlen(&id[i].str[1]);
		}
		max = 0;
		for(i = 1; i <= lenth[0]; i++)
		{
			pre(&id[0].str[i-1]);
			l = 10000;
			for(j = 1; j < N; j++)
			{
				tmp = 0;
				kmp(&id[0].str[i-1],id[j].str,j,lenth[0]-i+1);
				if(tmp < l)
					l = tmp;
			}
			if(l > max||(l==max&&l!=0&&strcmp(&id[0].str[i],ans)<0))
			{
				max = l;
				strcpy(ans,&id[0].str[i]);
				ans[l] = '\0';
			}
		}
		if(max==0)
			puts("IDENTITY LOST");
		else
			puts(ans);
	}
	return 0;
}