摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 建樹搜尋

例如:

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;
}