【AC自动机】zoj3228 Searching the String-白红宇

【AC自动机】zoj3228 Searching the String

阅读量：6786 次

发布时间：2019-06-26

本文共 577 字，大约阅读时间需要 1 分钟。

对所有模式串建立AC自动机。

每个单词结点要记录该单词长度。

然后在跑匹配的时候，对每个单词结点再处理3个值，代表可重叠的匹配次数，不可重叠的匹配次数，以及“上一次不可重叠的匹配位置”，这样结合单词长度就能保证不重叠。有多个重叠时，取靠前的位置更优。

Update：加了个优化，仅当某个结点的字符串的后缀可能是单词的时候，才会顺着fail指针往回跳。

#include
     
      #include
      
       #include
       
        using namespace std;queue
        
         q;bool word[601000];int child[601000][26],fail[601000],size,pos[101000];int cnta[601000],cntb[601000],posn[601000],lens[601000];void Insert(char S[],int id){    int len=strlen(S);    int now=0;    for(int i=0;i

转载于:https://www.cnblogs.com/autsky-jadek/p/6506324.html

你可能感兴趣的文章