垃圾題回來了
作法 : 建樹搜尋
例如:
5
abba
abaa
aa
abcd
adc
現在讀入第一行 abba
建出的樹
a
/
b
/
b
/
a
現在讀入第二行abaa
建出的樹
a
/
b
/\
b a
/ \
a a
現在讀入第三行aa
建出的樹
a
/ \
b a
/\
b a
/ \
a a
現在讀入第四行adc
建出的樹
a
/ \ \
b a d
/ /\ \
c b a c
/ / \
d a a
現在讀入第五行abcd
建出的樹
a
/ \
b a
/ /\
c b a
/ / \
d a a
如果要搜尋字串是否沒有出現 跑樹就對了!
/*************************************************************/
#include<stdlib.h>
#include<stdio.h>
int map[100000][26],top,time,used[100000],a,N;
char stop[100000],maptop[100000],s[30];
void DFS(int now,int L)
{
int a;
for(a=0;a<maptop[now];a++)
if(stop[map[now][a]]==s[L])
{
DFS(map[now][a],L+1);
return;
}
if(s[L]=='\0')
{
if(used[now]==0) used[now]=++time,printf("New! %d\n",time);
else printf("Old! %d\n",used[now]);
return;
}
if(maptop[now]==a)
{
map[now][maptop[now]++]=top;
stop[top++]=s[L];
DFS(map[now][a],L+1);
}
}
main()
{
while(scanf("%d",&N)==1)
{
time=0,top=26;
getchar();
while(N--)
{
gets(s);
DFS(s[0]-'a',1);
}
for(a=0;a<top;a++)
used[a]=0,maptop[a]=0,stop[a]=0;
}
return 0;
}