【字符串

admin 管理员组

文章数量: 887021

【字符串

一、总概述：

    在acm用到的算法中我觉得字符串类算法在实际中的应用价值可能最大，因为我们很多时候在和字符串打交道，在和匹配、查询打交道，比如我们按Ctrl+F的查找，目测有用Kmp匹配算法，linux下的fgrep利用AC自动机实现，还有很多的哈希方法也在各种实际应用中展现它的价值等等。

     本文针对AC自动机做个总结，并附带若干题解。

      建立AC自动机的一般步骤是:1、初始化根节点，根节点是所有字符串的前缀 2、利用模式串建立字典树(一般将主串叫匹配串，子串或去匹配的串叫模式串) 3、对字典树上的构建fail指针，fail指针指向当前串的最长后缀，这个后缀也是某个串的前缀，和KMP的next指针相似 4、利用构建好的ac自动机或者trie图(ac自动机的所有后继节点拓展之后就是trie图)进行操作，一般有查询、利用trie图建立矩阵、利用trie图进行状态DP等等。

     AC自动机（以下trie图也叫AC自动机)的精华是fail指针，上面有颜色的字是对fail指针的阐释，当匹配到p这个节点，如果后继节点失配了，那么总是找当前串的最长后缀也是某串的前缀的的后继节点去匹配，如果还不匹配继续找p->fail的最长后缀的后继结点去匹配，直到遇到能匹配的后继结点或者回溯到根节点重头再来。

    在字典树上构建fail指针是通过一个广搜来完成，从根节点开始像洪水般一层层向外构建fail指针，规定根节点的fail指针指向它自己。假设p点fail指针构建好了，q是p的后继结点也就是说q = p->next[k],除根为的所有节点都有q->fail = p->fail->next[k] ，特别的，当p是根时p->next[k]->fail  = root,显然根的第k个后继没办法匹配不可能再指向第k个后继，否则就陷入死循环.具体的过程见我的Hdu 2222代码。

     再说下如何将ac自动机改造成trie图，其实只需要一步就完成了。当我们匹配到p这个节点，如果它的后继节点失配了，ac自动机的做法是顺着fail指针一步一步回溯直到某点的后继结点匹配之或者到达根节点，而trie图就将这步改成O(1)的做法，最后匹配的那个节点直接赋给p的后继节点p->next[k].因为我们是一层层向外扩散，到达节点p，p->fail的next数组都已经赋好值，可以直接利用..这达到的效果正和fail指针的定义相一致。当我们在trie图上遍历出一条路径的时候，这条路径恰好表示一个串S，当遍历到节点p时，从根节点到p这条路径表示的串s为S的后缀。

     另外，我们还可以利用fail指针来方便的查找后缀，当我们反转fail指针后会得到一棵fail树，fail树中父亲节点是儿孙节点的后缀，当我们要查找含某些子串的父串时，利用这种树搭配着线段树或树状数组将十分飘逸，而我们要找当前节点代表的串的所有后缀，就可以从当前点找到根节点，这条路径上的节点在字典树中代表的串都是它的后缀。而字典树中父亲节点时儿孙节点的前缀，这两种树十分相似，所以我猜测fail树也具备很多性质。

二、题目列表：

1、 Hdu  2222 Keywords Search

2、Hdu 3695 Computer Virus on Planet Pandora

3、Poj 4052 Hrinity (金华邀请赛I)

4、Zoj 3430 Detect the Virus

5、Spoj 7758. Growing Strings

6、Hdu 4417 GRE Words

7、Spoj 1676. Text Generator

8、Hnu 10104 病毒

9、Hdu 2475 DNA repair

10、Hnu 11187 Emoticons :-)

11、Zoj 3545 Rescue the Rabbit

12、Hdu 3341 Lost's revenge

13、Zoj 3535 Gao the String II

14、Hdu 2243 考研路茫茫——单词情结

15、Hdu 3962 Microgene

16、大视野 2434 阿狸的打字机 

17、Hdu 3247 Resource Archiver

18、Zoj 3494 BCD Code

19、20...持续更新

三、简单题解

1、普通自动机

 Hdu  2222 Keywords Search

    模版题，普通的AC自动机照样不超时，但这题的数据太弱，很多人写搓了但是还能ac，最下面我附上本题的代码，并且带一些坑爹数据。

Hdu 3695 Computer Virus on Planet Pandora

    题目数据看上去很大，其实不然，用ac自动机可以轻松虐。先用模式串构建ac自动机，然后将主串解析成正常字符串，正反各查询一次就好了。

Poj 4052 Hrinity (金华邀请赛I)

    上题的加强版。但模式串不能出现某串是另一串的子串。本题要用到fa指针和fail指针，一个找当前串前缀一个找后缀，从从当前串的结束节点开始沿着fa指针和fail指针遍历到根节点，这两条路径上的节点到根节点的串便是当前串的子串，然后进行相应地处理即可。详细报告和测试数据见Here.

Spoj 7758. Growing Strings

    估计这题是2011年成都区域赛GRE那题的原题，但这题比较简单。题目给定n个字符串，让我们找出若干个字符串组成一个序列，前面一个字符串是后面一个字符串的子串，问我们能获得得最长序列的长度。因为先坐GRE那题，受那题思维束缚，死活要让这题的字符串从短到长，然后顺序就固定了，这样就按照GRE那题的做法，先离线建立ac自动机，然后一步步查询，然后就跪了。其实没要求顺序，本题就变得十分简单，我们要做的是找某个串的匹配部分和fail指针指向的最长后缀，取其中大者作为前序状态进行转移即可。这步在我们构造trie图的时候就可以边构造fail指针边进行转移。

Zoj 3430 Detect the Virus

   解析字符串，然后建立AC自动机查询之。

Hdu 4417 GRE Words

    2011年成都区域赛的题目，是上题的加强版，先建立ac自动机但不更新节点信息，构建完成之后进行查询、更新。具体报告见Here。

Spoj 1676. Text Generator

    题目给定n个熟悉的串，问长度为m且至少含一个熟悉串的方案数，m<=100万。逆向思维，用总的方案数减去不含熟悉串的方案数。先用ac自动机先求出一个矩阵，mat[i][j]表示从自动机的节点i不经过熟悉串的结尾有几种方法可以走到节点j。然后用mat矩阵进行二分快速幂，幂乘的时候注意尽量少用%mod。

Hnu 10104 病毒

    题目给定n个病毒串，问是否存在一个无限循环串都不包含这n个串。这题困扰了我很多天，我在建好AC自动机后尝试过很多解法，比如判断能不能回到根节点、将将两个相同的病毒串拼起来然后做n次插入等等，卡了好几天，不过我觉得这样挺好的，至少我的思维没被束缚。

   这题的本质是找到一个环，环上不包含所有的病毒串。正解是先构建AC自动机，改造成trie图，然后在trie图上顺着next数组进行深搜，如果搜到的一个节点在之前搜过，说明出现了环，否则就不存在这样的环。

2、自动机 + DP

Hdu 2475 DNA repair

     给定n个危险DNA序列，再给一段长度长为L的DNA序列S，DNA序列S中可能包含危险DNA序列，可以改变S中的字符，改变一个算一次操作，问最少操作几次可使S不含危险DNA序列，如果怎么操作都会含有危险DNA序列输出-1。

    比较简单的AC自动机+DP。状态转移方程:dp[i][j->next[k]] += min(dp[i-1][j] + (S[[i] == k))(dp[i][j]表示在我们构造解的过程中，长度为i且到j位置的最少操作数，不可达值为inf）

Hnu 11187 Emoticons :-)

    一开始我用类似上题的dp解本题，但是TLE了，因为复杂度为O(m*len*total)，len是主串长度，total为ac自动机节点总数，最坏的计算量为1920*8000，差不多1536，因为多组数据所以TLE了。再看一遍题目，我了个擦，原来是用空格来替换字符，而空格在模式串中都没出现过，这样用上面的DP就显得很鸡肋。后来YY了一个结论，如果碰到危险节点就滚回根节点，统计滚的次数。空格从未在模式串出现过，可知遇到空格的话就得滚回根节点，这很显然。我YY的结论貌似是按照题意去模拟，那么怎么保证次数最少呢？想想如果一个串还是病毒串，那么在这个串里肯定要替换一次，在最后替换对以当前串为前缀的串影响最大，所以必须选最后的危险节点，这个貌似YY但实则必然。Hnu的discuss里有个讲得比较多貌似比较靠谱的证明，大家可以看看，Here。

  这题用贪心过掉之后，就开始搞上题，改成贪心交上去就wa掉了，因为上题必须用ACTG去替换，替换完不一定回到根节点，这是本质的差别，所以不能用那么贪心。

Zoj 3545 Rescue the Rabbit

    利用这些串建立AC自动机，然后在自动机上DP.dp[i][j][k]表示长度为i在自动机上j位置状态为k是否可达。

    状态转移方程:if (dp[i][j][k] == true) dp[i+1][j->next[s]][newk].(实现的时候要用滚动数组，不然MLE).

    最后计算每个可达状态中的最大值。

Hdu 3341 Lost's revenge

   和上题相似，但要难些。因为是重组，考虑将ACGT进行状态压缩，单个A为1，单个C为1 * （num[A] + 1),单个G为(num[C] + 1) * (num[A] + 1)，单个T为(num[C] + 1) * (num[A] + 1)   * (num[G] + 1).然后在自动机上DP，dp[i][j]表示状态为i时到达位置j的最优值。状态转移方程和具体思路见Here   

Zoj 3535 Gao the String II

    要求用集合A中的串可重叠地构造出一个串，使得这个串含有最多的B集合中的串。利用B集合的串建立自动机，然后预处理A串哪些串可以重叠相连。设dp[i][j][k]表示长度为i的串匹配到位置j且最后的那个串为集合A中串k的最多含B串数。dp[nl][nj][s] = max(dp[nl][nj][s],dp[i][j][k] + ts),(ts为A中的串s从j位置开始匹配的路径中含有多少B串，nj为最后匹配到的位置).

    这题i的复杂度很可怕,O（len*(m*10)*n*n)，但运算量其实并不特别大，我的代码100msAC，名列第二.

3、自动机+矩阵

Hdu 2243 考研路茫茫——单词情结

   我们从反方向来想，计算都不含病毒串的方案数，然后用总方案数减去不含病毒串的方案数即可。利用单词构造AC自动机，然后利用自动机上的状态得到一个矩阵mat。用total - (mat^1+mat^2..mat^len)，后面的可以利用矩阵快速幂求得。具体解题报告见Here

Hdu 3962 Microgene

   我们需要构造一个(total *2 )* (total * 2)，类似于，第1行第一个1所代表的矩阵块表示怎么走都不经过病毒串的方案数，第二个1表示会经过一个串的方案数，第2行做辅助作用。具体解题报告见Here.

4、几道难题:

大视野 2434 阿狸的打字机 (NOI 好题)

   将trie图的指针反转建fail树，然后利用树状数组进行离线查询。好题，难题.具体报告见Here

Hdu 3247 Resource Archiver

   用代码串和病毒串建立自动机，他们在自动机上的差别是一个末节点标记，一个不标记。然后将每个代码串尾节点看做图上的一个节点，利用自动机计算每个串其他所有串的不重叠的最短长度即两两节点间的最短距离。最后转变成TSP问题，状态压缩DP解之.具体见Here。

Zoj 3494 BCD Code

    自动机和数位DP结合，需要对trie进行压缩，压缩成一个mat矩阵，mat[i][j]表示i位置下一个j的位置，j为数字0,1...9，找下一个位置是将0,1,2,..9编码成4位二进制,0001,0010,0011...然后在自动机上跑。具体见Here.

Hdu 2222 模版

1. #include <stdio.h>  
2. #include <string.h>  
3. #include <iostream>  
4. using namespace std;  
5. #define MIN 11000  
6. #define MAX 510000  
7.   
8.   
9. struct node {  
10.   
11.     int cnt,flag;  
12.     node *next[26],*fail;  
13. }tree[MAX],*root,*qu[MAX];  
14. int n,ans,ptr,head,tail;  
15. char str[MAX*2],dir[60];  
16.   
17.   
18. node *CreateNode() {  
19.   
20.     for (int i = 0; i < 26; ++i)  
21.         tree[ptr].next[i] = NULL;  
22.     tree[ptr].fail = NULL;  
23.     tree[ptr]t = tree[ptr].flag = 0;  
24.     return &tree[ptr++];   
25. }  
26. void Initial() {  
27.   
28.     ans = ptr = 0;  
29.     head = tail = 0;  
30.     root = CreateNode();  
31. }  
32. void Insert(char *str) {  
33.   
34.     int i = 0,k;  
35.     node *p = root;  
36.   
37.   
38.     while (str[i]) {  
39.   
40.         k = str[i++] - 'a';  
41.         if (p->next[k] == NULL)  
42.             p->next[k] = CreateNode();  
43.         p = p->next[k];  
44.     }  
45.     p->cnt++,p->flag = 1;  
46. }  
47. void Build_AC() {  
48.   
49.     qu[head++] = root;  
50.     while (tail < head) {  
51.   
52.         node *p = qu[tail++];  
53.         for (int k = 0; k < 26; ++k)  
54.             if (p->next[k]) {  
55.               
56.                 if (p == root) p->next[k]->fail = root;  
57.                 else {  
58.                       
59.                     p->next[k]->fail = p->fail->next[k];  
60.                     if (!p->next[k]->flag) p->next[k]->cnt = 1;  
61.                     //象征性地表示以当前点的所有后缀是否有危险节点  
62.                 }  
63.                 qu[head++] = p->next[k];  
64.             }  
65.             else {  
66.   
67.                 if (p == root) p->next[k] = root;  
68.                 else p->next[k] = p->fail->next[k];  
69.             }  
70.     }  
71. }  
72. int Query(char *str) {  
73.   
74.     node *p = root;  
75.     int i = 0,k,cnt = 0;  
76.   
77.   
78.     while (str[i]) {  
79.   
80.         k = str[i++] - 'a';  
81.         p = p->next[k];  
82.         if (p->cnt) {  
83.   
84.             node *temp = p;  
85.             while (temp != root) {  
86.   
87.                 if (temp->flag) cnt += temp->cnt;  
88.                 temp->cnt = 0,temp = temp->fail;  
89.             }  
90.         }  
91.     }  
92.   
93.   
94.     return cnt;  
95. }  
96.   
97.   
98. int main()  
99. {  
100.     int i,j,k,t;  
101.   
102.   
103.     scanf("%d",&t);  
104.     while (t--) {  
105.   
106.         scanf("%d",&n);  
107.         Initial();  
108.         for (i = 1; i <= n; ++i)  
109.             scanf("%s",dir),Insert(dir);  
110.   
111.   
112.         Build_AC();  
113.         scanf("%s",str);  
114.         ans = Query(str);  
115.         printf("%d\n",ans);  
116.     }  
117. }  

Hdu 2222 数据：

1. Input:  
2. 5  
3. 3  
4. b  
5. bac  
6. abcd  
7. abcba  
8.   
9. 4  
10. abcd  
11. bcde  
12. cd  
13. d  
14. abcde  
15.   
16. 2  
17. sher  
18. he  
19. she  
20.   
21. 2  
22. sher  
23. he  
24. sher  
25.   
26. 6  
27. abc  
28. abc  
29. abc  
30. bc  
31. aabc  
32. aabcaa  
33. aaaaaaaabcbccccc  
34.   
35. OutPut:  
36. 1  
37. 4  
38. 1  
39. 2  
40. 5  

本文标签： 字符串