[JSOI2010 Word Query 电子字典]Trie

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1819
【算法分析】
Trie+直接暴力枚举那些操作。
【其它】1A。跑得再一次全世界最慢。
【CODE】
#include #include #include int n,m;
struct Trie_t{
Trie_t *son[26];int key;
void Fill(){
for (int i=0;i<26;i++) son[i]=NULL;
key=0;
}
}*root;

void Insert(char *str){
Trie_t *p=root;
while (*str){
if (p->son[*str-‘a’]) p=p->son[*str-‘a’];
else{
p->son[*str-‘a’]=(Trie_t*)malloc(sizeof(Trie_t));
p=p->son[*str-‘a’];
p->Fill();
}
str++;
}
p->key++;
}

void input(){
root=(Trie_t*)malloc(sizeof(Trie_t));
root->Fill();
char str[100];
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",str);
Insert(str);
}
}

bool Find(char *str){
Trie_t *p=root;
while (*str){
if (!p->son[*str-‘a’]) return false;
p=p->son[*str-‘a’];
str++;
}
if (p->key) return true;
return false;
}

void solve(){
char str[100],str2[100],Inchar;
for (int i=1,j,k,Inchar;i<=m;i++){
scanf("%s",str);
if (Find(str)) puts("-1");
else{
int Len=strlen(str),tot,ans=0;
for (j=0;j if (str[j]==str[j+1]) continue;
tot=0;
for (k=0;k if (k!=j)
str2[tot++]=str[k];
str2[tot]=0;
if (Find(str2)) ans++;
}

for (j=0;j<=Len;j++)
for (Inchar=’a’;Inchar<='z';Inchar++){
if (str[j]==Inchar) continue;
tot=0;
for (k=0;k str2[tot++]=str[k];
str2[tot++]=Inchar;
for (k=j;k str2[tot++]=str[k];
str2[tot]=0;
if (Find(str2))
ans++;
}

for (j=0;j char tmp=str[j];
for (Inchar=’a’;Inchar<='z';Inchar++){
str[j]=Inchar;
if (Find(str)) ans++;
}
str[j]=tmp;
}
printf("%dn",ans);
}
}
}

int main(){
input();
solve();
}