| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
AC用字典树做的,不过效果不太好1325MS#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define max 100005
struct node
{
int v;
int temp;
struct node*next[10];
};
struct node*newnode()
{
struct node*r;
r=new struct node;
r->v=r->temp=0;
int i;
for(i=0;i<10;i++)
r->next[i]=NULL;
return r;
}
int insert(struct node*root,string str)
{
int i;
struct node *r,*s;
r=root;
int flag=0;
for(i=0;i<str.length();i++)
{
if(str[i]=='-')continue;
if(r->next[str[i]-'0']==NULL)
{
s=newnode();
s->v=1;
r->next[str[i]-'0']=s;
r=s;
}
else
{
r=r->next[str[i]-'0'];
r->v++;
flag++;
}
}
r->temp=1;
if(flag==7)return 1;
return 0;
}
int search(struct node*root,string str)
{
struct node*r;
r=root;
int i;
for(i=0;i<str.length();i++)
{
if(str[i]=='-')continue;
r=r->next[str[i]-'0'];
}
return r->v;
}
struct ca
{
char str[100];
int sum;
}s[max];
int cmp(struct ca a,struct ca b)
{
if(strcmp(a.str,b.str)==-1)
return 1;
return 0;
}
char match[26]={"222333444555666777888999"};
int main()
{
int n;
cin>>n;
struct node*root;
root=newnode();
int i=0;
while(n--)
{
char temp[100];
scanf("%s",temp);
int L=strlen(temp);
int k=0;
int j;
for(j=0;j<L;j++)
{
if(temp[j]=='Z'||temp[j]=='Q'||temp[j]=='-')
continue;
else if(temp[j]<'Q'&&temp[j]>='A')
s[i].str[k]=match[(temp[j]-'A')];
else if(temp[j]>'Q'&&temp[j]<='Z')
s[i].str[k]=match[temp[j]-'A'-1];
else
s[i].str[k]=temp[j];
k++;
if(k==3)
{s[i].str[k]='-';k++;}
}
s[i].str[k]='\0';k++;
if(!insert(root,s[i].str)){i++;}
}
sort(s,s+i,cmp);
int tag=0;int j;
for(j=0;j<i;j++)
{
int t=search(root,s[j].str);
if(t>=2)
{
tag=1;
printf("%s %d\n",s[j].str,t);
}
}
if(!tag)printf("No duplicates.\n");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator