第一种方法。。较为繁琐，用字典序写的，用空间来换时间
[cpp]
#include
#include
using namespace std;
typedef struct trietree* Ptree;
struct trietree
{
bool arrive;
int treenum;
Ptree next[10];
} node[1000000];
int size;
bool findsolve;
void newtree(int no)
{
int i;
node[no].arrive=false;
node[no].treenum=0;
for(i=0; i<=9; i++)
{
node[no].next[i]=NULL;
}
}
int dispose(char *p)
{
int num=0;
char *q=p;
while(*++p!='\0');
p--;
while(p>=q)
{
if(*p=='-')
{
p--;
continue;
}
num*=10;
if(*p>='A'&&*p<='Y')
num+=(*p-'A'-(*p>'Q'))/3+2;
else if(*p>='0'&&*p<='9')
num+=*p-'0';
p--;
}
return num;
}
void addnum(int num)
{
Ptree p=&node[1];
int i,k;
for(i=0; i<=6; i++)
{
k=num%10;
num/=10;
if(!p->next[k])
{
newtree(++size);
p->next[k]=&node[size];
}
p=p->next[k];
}
p->arrive=true;
p->treenum++;
return ;
}
void dfs(char phone[9],int m,Ptree p)
{
if(true==p->arrive)
{
if(p->treenum>1)
{
for(int i=1; i<=7; i++)
{
if(i==4)
printf("-");
printf("%c",phone[i]);
}
printf(" %d\n",p->treenum);
findsolve=true;
}
return ;
}
for(int i=0; i<=9; i++)
{
if(p->next[i])
{
phone[m+1]=i+'0';
dfs(phone,m+1,p->next[i]);
}
}
return ;
}
int main()
{
int n,i,j;
int number;
char phone[9];
char ch[80];
scanf("%d",&n);
size=1;
newtree(1);
for(i=1; i<=n; i++)
{
scanf("%s",ch);
number=dispose(ch);
addnum(number);
}
dfs(phone,0,&node[1]);
if(!findsolve)
printf("No duplicates.\n");
return 0;
}
#include
#include
using namespace std;
typedef struct trietree* Ptree;
struct trietree
{
bool arrive;
int treenum;
Ptree next[10];
} node[1000000];
int size;
bool findsolve;
void newtree(int no)
{
int i;
node[no].arrive=false;
node[no].treenum=0;
for(i=0; i<=9; i++)
{
node[no].next[i]=NULL;
}
}
int dispose(char *p)
{
int num=0;
char *q=p;
while(*++p!='\0');
p--;
while(p>=q)
{
if(*p=='-')
{
p--;
continue;
}
num*=10;
if(*p>='A'&&*p<='Y')
num+=(*p-'A'-(*p>'Q'))/3+2;
else if(*p>='0'&&*p<='9')
num+=*p-'0';
p--;
}
return num;
}
void addnum(int num)
{
Ptree p=&node[1];
int i,k;
for(i=0; i<=6; i++)
{
k=num%10;
num/=10;
if(!p->next[k])
{
newtree(++size);
p->next[k]=&node[size];
}
p=p->next[k];
}
p->arrive=true;
p->treenum++;
return ;
}
void dfs(char phone[9],int m,Ptree p)
{
if(true==p->arrive)
{
if(p->treenum>1)
{
for(int i=1; i<=7; i++)
{
if(i==4)
printf("-");
printf("%c",phone[i]);
}
printf(" %d\n",p->treenum);
findsolve=true;
}
return ;
}
for(int i=0; i<=9; i++)
{
if(p->next[i])
{
phone[m+1]=i+'0'