耽擱了很久的題目，突然想起來了這題還沒做，這幾天做了幾道字典樹，就拿來用字典樹做一做。速度不是很快，空間用的很大。至少ac了……
#include<iostream>
#include<cstring>
using namespace std;
int n;
char tmp[100];//輸入字符串
struct list
{
int val;//7位數(shù)字的值
int num[8];//7位數(shù)字
}s[100001];//輸入的list
struct ans
{
int val;
int num[8];
}xx[101];//滿足cnt>=2的list
struct Trie
{
int next[10];
int cnt;
void init(){memset(next,-1,sizeof(next));cnt=0;}
};
Trie T[200001];
int p,q=0;
int cmp(const void *a,const void *b)//按val值排序
{
struct ans *c=(ans*)a;
struct ans *d=(ans*)b;
return c->val>d->val?1:-1;
}
int turn(char c[],int t)//將字符串轉換為數(shù)字
{
int i,j;
j=0;
for(i=0;i<strlen(c);i++)
{
if(c[i]>='A'&&c[i]<='C')
{
s[t].num[j++]=2;
}
else if(c[i]>='D'&&c[i]<='F')
{
s[t].num[j++]=3;
}
else if(c[i]>='G'&&c[i]<='I')
{
s[t].num[j++]=4;
}
else if(c[i]>='J'&&c[i]<='L')
{
s[t].num[j++]=5;
}
else if(c[i]>='M'&&c[i]<='O')
{
s[t].num[j++]=6;
}
else if(c[i]>='P'&&c[i]<='S')
{
s[t].num[j++]=7;
}
else if(c[i]>='T'&&c[i]<='V')
{
s[t].num[j++]=8;
}
else if(c[i]>='W'&&c[i]<='Y')
{
s[t].num[j++]=9;
}
else if(c[i]>='0'&&c[i]<='9')
{
s[t].num[j++]=c[i]-'0';
}
}
s[t].val=s[t].num[0]*1000000+s[t].num[1]*100000+s[t].num[2]*10000+s[t].num[3]*1000+s[t].num[4]*100+s[t].num[5]*10+s[t].num[6];
}
int build()//建樹
{
p=1;
T[p].init();
return 0;
}
int insert(int c[],int t)//插入電話號碼
{
int indx=1;
int i,j;
for(i=0;i<7;i++)
{
if(T[indx].next[c[i]]==-1)
{
T[indx].next[c[i]]=++p;
T[p].init();
}
indx=T[indx].next[c[i]];
}
T[indx].cnt++;
if(T[indx].cnt==2)
{
memcpy(xx[q].num,s[t].num,sizeof(s[t].num));
xx[q++].val=s[t].val;
}
}
int check(int c[])//查找>2的電話條目的cnt
{
int i;
int indx=1;
for(i=0;i<7;i++)
{
indx=T[indx].next[c[i]];
}
return T[indx].cnt;
}
int main()
{
int n;
int i,j;
scanf("%d",&n);
build();
for(i=1;i<=n;i++)
{
scanf("%s",tmp);
turn(tmp,i);
insert(s[i].num,i);
}
if(q==0)
{
printf("No duplicates.\n");
return 0;
}
else
{
qsort(xx,q,sizeof(xx[0]),cmp);
for(i=0;i<q;i++)
{
for(j=0;j<3;j++)
{
printf("%d",xx[i].num[j]);
}
printf("-");
for(;j<7;j++)
{
printf("%d",xx[i].num[j]);
}
printf(" ");
printf("%d\n",check(xx[i].num));
}
}
system("pause");
return 0;
}