我用KMP算法一个个比较，超时了。哪位高手能点拨一下思路。谢谢！
#include <stdio.h>
#include <string.h>
#include <math.h>
struct node
{
	char str[30];
	int count;
	int next[30];
}s1[100];
void change(char a[])
{
	int i,j;
	for (i=0,j=0;a[i];i++)
	{
		if (a[i]>='A'&&a[i]<='Z')
			a[j++]=a[i]-'A'+'a';
		else if((a[i]>='a'&&a[i]<='z')||(a[i]>='0'&&a[i]<='9')||a[i]==' ')
			a[j++]=a[i];
	}
	a[j]='\0';
}
void GetNext(char t[],int next[])
{
	int j,k,l;
	j=0;k=-1;next[0]=-1;
	l=strlen(t);
	while(j<l-1)
	{
		if (k==-1||t[j]==t[k])
		{
			j++;
			k++;
			next[j]=k;
		}
		else
			k=next[k];
	}
}
void KMP_Count(char a[],char t[],int *n,int next[])
{
	int i,j,l1,l2;
	*n=0;
	i=0;
	l1=strlen(a);
	l2=strlen(t);
	while (a[i])
	{
		j=0;
		while(i<l1&&j<l2)
			if(j==-1||a[i]==t[j])
			{
				i++;
				j++;
			}
			else
				j=next[j];
	if(t[j]=='\0')
		(*n)++;
	}
}
void main()
{
	char s[300],a[300],b[20],t[50];
	int i,j,k,sum,n,max;
	float result;
	gets(s);
	gets(b);
	change(s);
	for(i=0;i<100;i++)
		s1[i].count=0;
	i=0;
	max=0;
	while (s[i])
	{
		if(s[i]==' ')i++;
		j=0;
		while(s[i]&&s[i]!=' ')
			t[j++]=s[i++];
		t[j]='\0';
		for(k=0;k<max;k++)
			if (strcmp(t,s1[k].str)==0)
			{
				s1[k].count++;
				break;
			}
		if(k==max)
		{
			strcpy(s1[max].str,t);
			s1[max].count++;
			max++;
		}
	}
	for(i=0;i<max;i++)
		GetNext(s1[i].str,s1[i].next);
	gets(a);
	while(strcmp(a,"----------")!=0)
	{
		gets(b);
		change(a);
		n=0;
		result=0;
		i=0;
		while(i<max)
		{
			KMP_Count(a,s1[i].str,&n,s1[i].next);
			if(n)
			{
				sum=n*s1[i].count;
				result+=sqrt(sum);
			}
			i++;
		}
		printf("%.2f\n",result);
		gets(a);
	}
}

• hash (0) 20053565 2008-11-23 18:14:52