3529363_wa.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 88 行

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

int N, tmp;
struct node
{
	char str[10001];
}id[2];

int pai[210];
int changdu[4010];

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

	pai[1] = 0;
	k = 0;
	for(q = 2; q <= changdu[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 <= changdu[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;
	int cas;

	scanf("%d", &cas);
	getchar();
	while(cas-- > 0)
	{
		N = 2;
		for(i = 0; i < N; i++)
		{
			gets(&id[i].str[1]);
			changdu[i] = strlen(&id[i].str[1]);
		}
		max = 0;
		for(i = 1; i <= changdu[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,changdu[0]-i+1);
				if(tmp < l)
					l = tmp;
			}
			if(l > max)
			{
				max = l;
			}
		}
		printf("Nejdelsi spolecny retezec ma delku %d.\n", max);
	}
	return 0;
}