sorry for posting my code here, but i cannot get AC after many WA..
i use the algoritms sohel said at first, and it is ok for
cat
cat
dog
lion
#
c a t
#
can anyone help me? Thanks a lot..!!
Code: Select all
#include <stdio.h>
#include <string.h>
int ndic=0,n,u[7],ans;
char s[10000],dic[1000][11],d[8][2],word[8],c,*p;
void subset(int,int);
int BSearch();
main(){
int i;
for(i=0;i<7;i++) u[i]=0;
while(scanf("%s%c",s,&c) && s[0]!='#')
strcpy(dic[ndic++],s);
while(gets(s) && s[0]!='#'){
n=ans=0;
p=strtok(s," ");
strcpy(d[n++],p);
while((p=strtok(NULL," "))!=NULL)
strcpy(d[n++],p);
for(i=1;i<=n;i++) //generate all the permutations
subset(0,i);
printf("%d\n",ans);
}
}
void subset(int level,int len){
if(level==len){
word[len]='\0';
ans+=BSearch();
return;
}
int i;
char pre='-';
for(i=0;i<n;i++)
if(!u[i] && d[i][0]!=pre){
u[i]=1;
pre=d[i][0];
word[level]=d[i][0];
subset(level+1,len);
u[i]=0;
}
}
int BSearch(){ //search for word[] in dic[]
int left=0,right=ndic-1,mid,r,flag,i;
while(left<=right){
mid=(left+right)/2;
flag=strcmp(word,dic[mid]);
if(flag==0){
r=1;
//the same words in the dictionary?
for(i=mid-1;i>=0 && strcmp(word,dic[i])==0;i--,r++);
for(i=mid+1;i<ndic && strcmp(word,dic[i])==0;i++,r++);
return r;
}
if(flag<0) right=mid-1;
else left=mid+1;
}
return 0; //not found
}