UVA 1149 Dominating Patterns

 

解析：先用word[][]保存单词，然后利用AC自动机来求哪些字符串是匹配的。作为AC自动机入门题目，如果不了解AC自动机的话可以参考http://blog.csdn.net/niushuai666/article/details/7002823，业界良心。AC自动机还有一题入门题，hdu 2222,如果大家有时间的话，可以去看一下。附上我的结题报告链接http://blog.csdn.net/hehedounima/article/details/12184245（貌似这里面关于AC自动机我的注释更详细）

 

#include"stdio.h"  
#include"string.h"  
#include"queue"  
using namespace std;  
#define Max 1000010  
  
#define maxnode (150*70+10)  
#define sigma_size 26  
int num[maxnode],flag[maxnode];  
char word[151][71];  
struct AC_automation{             
    struct node{  
        int next[sigma_size];  
        int val;      
        int fail;     
        void init(){  
            memset(next,0,sizeof(next));  
            fail = val = 0;  
        }  
    }ch[maxnode];     
    int sz;                           
    int idx(char c){  
        return c - 'a';       
    }  
  
    void init(){  
        sz = 1;  
        ch[0].init();  
    }  
    void insert(char *s,int x){  
        int u = 0;  
        for(int i = 0 ; s[i] ; i ++){  
            int c = idx(s[i]);  
            if(ch[u].next[c] == 0){       
                ch[sz].init();  
                ch[u].next[c] = sz++;     
            }  
            u = ch[u].next[c];  
        }  
        ch[u].val = 1;  
        flag[u] = x;  
    }  
  
      
    void get_fail(){  
        queue<int>Q;  
        for(int i = 0 ; i < sigma_size; i ++)  
            if(ch[0].next[i] != 0)  
                Q.push(ch[0].next[i]);  
        while(!Q.empty()){  
            int temp = Q.front();  
            Q.pop();  
            for(int i = 0 ; i < sigma_size; i ++){  
                if(ch[temp].next[i] != 0){  
                    Q.push(ch[temp].next[i]);  
                    int fail_temp = ch[temp].fail;  
                    while(fail_temp > 0 && ch[fail_temp].next[i] == 0)   
                        fail_temp = ch[fail_temp].fail;  
                    if(ch[fail_temp].next[i] != 0)    
                            fail_temp = ch[fail_temp].next[i];  
                    ch[ch[temp].next[i]].fail = fail_temp;    
                }  
            }  
        }  
    }  
  
    //求出现次数最多的单词  
    void get_maxnum(char *text){  
        int temp = 0;  
        for(int i = 0 ; text[i] ; i ++){  
            int character = idx(text[i]);  
            while(ch[temp].next[character] == 0){  
                if(temp == 0)  //如果是根节点仍然没有匹配  
                    break;  
                temp = ch[temp].fail;  
            }  
            if(ch[temp].next[character]){  
                temp = ch[temp].next[character];  
                if(ch[temp].val)  
                    num[temp]++;  //num[i]用来记录i节点单词出现的次数  
            }  
        }  
    }  
}AC;  
  
char text[Max];  
int N;  
  
int main(){  
    while(scanf("%d",&N) != EOF && N != 0){  
        AC.init();  
        memset(flag,0,sizeof(flag));  
        memset(word,0,sizeof(word));  
        memset(num,0,sizeof(num));  
        memset(text,0,sizeof(text));  
        char str_temp[75];  
        for(int i = 0 ; i < N; i ++){  
            scanf("%s",word[i]);  
            AC.insert(word[i],i);  
        }  
        AC.get_fail();  
        scanf("%s",text);  
        AC.get_maxnum(text);  
        int max  = -1;  
        for(int i = 1 ; i < AC.sz; i ++)  
            if(max < num[i])  
                max = num[i];  
        printf("%d\n",max);  
        for(int i = 1 ; i < AC.sz; i ++)  
            if(num[i] == max){  
                printf("%s\n",word[flag[i]]);  
            }  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,