hihocoder1036 trie图

trie图用于解决多模式匹配问题。设有N个长度不超过L的模式串，匹配串长为M，那么用trie图解决多模式匹配问题的复杂度为O(N*L+M).

思路:

trie图的基础是trie树。

1.用trie树实现多模式匹配

　　首先建立N个模式串的trie树。设匹配串为s，我们枚举匹配起始位置i，在trie树中依次去查询字典中是否有字符串&str[i]的前缀。这样做的复杂度为O(M*L).

2.用trie图实现多模式匹配

　　对于上述用trie树实现多模式匹配的方式，当我们沿trie树匹配的过程中找不到当前字符对应的边的时候，我们的做法是改变起始位置i的值，从trie树根节点从头再来。

　　但其实此时我们已经从s的当前起始点i开始成功匹配了k个字符，那么我们在枚举下一个起点i+1的时候，意味着前k-1个字符已经在上一次枚举中匹配过了，就像kmp算法一样，如果我们能利用好这个信息，就能大大的减小时间复杂度。

2.1后缀节点的概念

　　假设从根节点到当前节点A的路径所对应的字符串为"abcde"，那么"bcde"所对应的路径末节点就是节点A的后缀节点。但是，trie树中可能并不存在"bcde"这样一条从根节点开始的路径，此时A的后缀节点是"bcde"的后缀节点，即后缀节点的后缀节点，如此递归。特别的，根节点的后缀节点为根节点，深度为1的节点的后缀节点也为根节点。

2.2后缀节点的求法

　　采用广度优先遍历来求解后缀节点，这样，当我们要求trie树中第i层节点的后缀节点的时候，第0~i-1层的所有点的后缀节点都已知了。我们可以根据父节点来求当前节点的后缀节点：假设父节点到当前节点的边为ch，那么当前节点的后缀节点就是父节点的后缀节点通过ch这样一条边所到达的节点。然而，父节点的后缀节点有可能并不存在ch这样一条边，此时，我们需要看后缀节点的后缀节点是否存在ch这样一条边，如此递归。但是，如果我们每次都这样递归来做未免显得有些麻烦，所以，在bfs的时候，对于每个节点，我们用一个数组记录下从当前节点经过每一个ch所到达的节点，这里的“到达”的理解：当存在ch边的时候，就是一般意义的到达，当不存在ch边的时候，这里的“到达”应该理解为其后缀节点经过ch这样一条边所到达的节点。如此一来，后缀节点的求解就很简单了。

　　还有一个问题需要注意：当当前节点不存在匹配字符所对应的边即不匹配的时候，我们直接跳转到其后缀节点，然后继续往下匹配，我们这种做法会可能造成一种后果：那就是从根节点到后缀节点的路径中可能存在标记节点，而被我们忽略了。解决这个问题的方法是“在求解当前后缀节点的过程中，若求得的后缀节点是标记节点，那么当前节点也要被标记”。

2.3实现多模式匹配

　　求得了所有的后缀节点，相当于我们的trie图已经构建完毕了。此时，多模式匹配问题，就只需要遍历匹配串，从trie树的根节点开始逐个字符匹配，当匹配不成功的时候，就跳转到后缀节点继续匹配，直到匹配成功或者匹配串遍历结束。

我的代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define MAXN 1000005
  8 #define MAX_CH 26
  9 
 10 char str[MAXN];
 11 int nodecnt;
 12 
 13 struct trieNode
 14 {
 15     trieNode *p[MAX_CH]; 
 16     trieNode *pFather;
 17     int ch; 
 18     bool isMarked;
 19     trieNode *postfix;
 20     trieNode *next[MAX_CH];
 21     
 22     void init()
 23     {
 24         for(int i=0; i<MAX_CH; ++i)
 25         {
 26             p[i] = NULL;
 27             next[i] = NULL;
 28         }
 29         isMarked = 0;
 30         postfix = NULL;
 31     }
 32 }node[MAXN];
 33 
 34 struct Trie
 35 {
 36     trieNode *root;
 37     
 38     void init()
 39     {
 40         root = &node[0];
 41         root->init();
 42         root->pFather = NULL;
 43         root->ch = -1;
 44         
 45         nodecnt = 1;
 46     }
 47     
 48     //向trie中插入单词 
 49     void insert(char *str)
 50     {
 51         trieNode *pNow = root;
 52         int len = strlen(str);
 53         for(int i=0; i<len; ++i)
 54         {
 55             int id = str[i]-'a';
 56             if(pNow->p[id]==NULL)
 57             {
 58                 pNow->p[id] = &node[nodecnt++];
 59                 pNow->p[id]->init();
 60                 pNow->p[id]->pFather = pNow;
 61                 pNow->p[id]->ch = id;
 62             }
 63             if(i==len-1)
 64             {
 65                 pNow->p[id]->isMarked = 1;
 66             }
 67             pNow = pNow->p[id];
 68         }
 69     }
 70     
 71     //求某个节点的后缀节点 
 72     void getPostfix(trieNode *pNow)
 73     {
 74         if(pNow==root)
 75         {
 76             pNow->postfix = pNow;
 77             
 78             for(int i=0; i<MAX_CH; ++i)
 79             {
 80                 if(pNow->p[i]!=NULL)
 81                 {
 82                     pNow->next[i] = pNow->p[i];
 83                 }
 84                 else
 85                 {
 86                     pNow->next[i] = pNow;
 87                 }
 88             }
 89         }
 90         else
 91         {
 92             if(pNow->pFather==root)
 93             {
 94                 pNow->postfix = root;
 95             }
 96             else
 97             {
 98                 pNow->postfix = pNow->pFather->postfix->next[pNow->ch];
 99             }
100             if(pNow->postfix->isMarked)
101             {
102                 pNow->isMarked = 1;
103             }
104             
105             for(int i=0; i<MAX_CH; ++i)
106             {
107                 if(pNow->p[i]!=NULL)
108                 {
109                     pNow->next[i] = pNow->p[i];
110                 }
111                 else
112                 {
113                     pNow->next[i] = pNow->postfix->next[i];
114                 }
115             }
116         }    
117     }
118     
119     //广度优先遍历，求所有节点的后缀节点, 构造trie图 
120     void bfs()
121     {
122         queue<trieNode*> q;
123         q.push(root);
124         while(!q.empty())
125         {
126             trieNode *pNow = q.front();
127             getPostfix(pNow);
128             q.pop();
129             for(int i=0; i<MAX_CH; ++i)
130             {
131                 if(pNow->p[i]!=NULL) q.push(pNow->p[i]);
132             }
133         }    
134     }
135     
136     //多模式匹配 
137     bool match(char *str)
138     {
139         trieNode *pNow = root;
140         int len = strlen(str);
141         
142         for(int i=0; i<len; ++i)
143         {
144             int id = str[i]-'a';
145             if(pNow->p[id]==NULL)
146             {
147                 pNow = pNow->postfix;
148                 if(pNow->isMarked) return 1;
149             }
150             pNow = pNow->next[id];
151             if(pNow->isMarked) return 1;
152         }
153         return 0;
154     }
155 }trie;
156 
157 int main()
158 {
159     int n;
160     while(scanf("%d", &n)!=EOF)
161     {
162         trie.init();
163         while(n--)
164         {
165             scanf("%s", str);
166             trie.insert(str);
167         }
168         trie.bfs();
169         scanf("%s", str);
170         puts(trie.match(str)?"YES":"NO");
171     }
172     return 0;
173 }

题目来源:http://hihocoder.com/problemset/problem/1036