又叫Rabin-Karp算法,下面是我的程序,受用了这个算法思想启发,可就是WA,大牛帮我看看错在哪里,小弟感激不尽:
#include "stdio.h"
#include "string.h"
struct {
int h,l,t,ne;
}s[100000];
int h[100000]={0};
int l[100000]={0};
char da[100000][25];
int main() {
 	int n,i,j,p,f,b,d,u;
	char c;
	scanf("%d",&n);
	for(j=0;j<n;j++)scanf("%s",da[j]);
	for(j=0;j<n;j++){
	u=strlen(da[j]);
	d=b=0;
	for(i=0;i<u;i++){
		c=da[j][i];
	  if(c!='-'){
		if(c>='0'&&c<='9')p=c-'0';
		else if(c>='A'&&c<='Y')p=(c<'Q'?(c-'A'):(c-'B'))/3+2;
		if(b==7)break;
		if(b<=3){h[j]=h[j]*10+p;b++;}
		else {l[j]=l[j]*10+p;b++;}
	  }
	}
	}
	s[0].h=s[0].l=s[0].ne=-1;
	s[0].t=0;
	j=1;
	for(i=0;i<n;i++){
	f=p=0;
	d=h[i]*10000+l[i];
	while(s[p].ne!=-1&&d>(s[p].h*10000+s[p].l)){f=p;p=s[p].ne;}
	if(d==(s[p].h*10000+s[p].l))s[p].t++;
	else	if(d<(s[p].h*10000+s[p].l))
	{
		s[j].h=h[i];
		s[j].l=l[i];
		s[j].t=1;
		s[j].ne=p;
		s[f].ne=j;
		j++;
	}
	else{
		s[j].h=h[i];
		s[j].l=l[i];
		s[j].t=1;
		s[j].ne=s[p].ne;
		s[p].ne=j;
		j++;
	}
	}
	b=p=0;
	while(s[p].ne!=-1)
	{
		if(s[s[p].ne].t>1)
		{	printf("%03d-%04d %d\n",s[s[p].ne].h,s[s[p].ne].l,s[s[p].ne].t);
			b=1;
		}
			p=s[p].ne;
	}
	if(b==0)printf("No duplicates.\n");
	return 0;
}

• Rabin-Karp. (0) 497597816 2007-06-13 20:17:23
  • 晕，又被耍了。。 (4) richardxx 2007-06-13 20:58:59
    • richardxx说话请负点责任，谁耍你了？！ (0) 497597816 2007-06-15 13:58:32
      • Re:关于这个算法请参照刘汝佳和黄亮编的　算法艺术与信息学竞赛　一书，你没看过别乱说！ (0) 497597816 2007-06-15 14:01:30
      • 你先看看题目和这几个贴的意思…… (0) frkstyc 2007-06-15 14:27:53
      • 不好意思，其实我是想表达关于RB算法的回答没有使我很惊讶而发出的感叹，不是说你欺骗哈.. (4) richardxx 2007-06-15 18:20:42