HDU 6138 Fleet of the Eternal Throne 多校#8 AC自动机-白红宇

HDU 6138 Fleet of the Eternal Throne 多校#8 AC自动机

阅读量：4946 次

发布时间：2019-06-11

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

给n个串，每次询问x号串和y号串的最长公共子串的长度，这个子串必须是n个串中某个串的前缀

做法是把n个串建成AC自动机，前缀树中每个节点都当做结尾节点，val赋为trie树深度

然后把x串丢进自动机里，把匹配到的前缀节点染个色，再把y串丢进去，遇到同样颜色的前缀节点就更新一下答案

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                using namespace std;#define ll long long#define pb push_back#define FOR(a) for(int i=1;i<=a;i++)const int inf=0x3f3f3f3f;const int maxn=1e5+91; const int mod=1e9+7;const int sigma=26;struct automata{ int ch[maxn][sigma]; int val[maxn]; int f[maxn]; int color[maxn]; int sz; int newnode(){ memset(ch[sz],0,sizeof(ch[sz])); f[sz]=val[sz]=color[sz]=0; return sz++; } void init(){ memset(val,0,sizeof(val)); sz=0; newnode(); } void insert(char *s,int v){ int u=0; int len=strlen(s); for(int i=0;i