大家好，又见面了，我是你们的朋友全栈君。

Fleet of the Eternal Throne

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 291    Accepted Submission(s): 131

  
  
  

   
   
   1
3
aaa
baaa
caaa
2
2 3
1 2
  
  
  

  
  
  

   
   
   3
3
  
  
  

题解：对n个串造出 自动AC机 ，这里的AC机不需要维护单词的结束点  需要维护一个每个节点到根的距离，也就是前缀的长度。然后用x跑一遍AC机，在所有匹配成功的结束节点上记上一个标记（直接记成询问次数就行了：第一次询问flag记成1，第二次记成2，这样保证每次的flag都不一样就不用清空标记了），然后这些标记点的意思就是：这个前缀是n个串中某个的前缀，且这个前缀是串x的字串。然后再用y跑一次AC机，在y匹配成功的节点，如果他刚刚被打了标记，那就统计最长的length就可以。对于每个节点都要打标记，不是在字母最后一个地方打。。

原来模板太不好变化了。。有改了下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e6 + 7;
const int maxnode = 50*10010;
int n;
char s1[60], s2[maxn];
int pos[maxn];
struct node
{
    int ch[maxnode][26], cnt[maxnode], fail[maxnode], last[maxnode], id, road[maxnode]; // 路径压缩优化， 针对模式串出线的种类
    int dep[maxnode], flag[maxnode];
    void init()
    {
        memset(ch[0], 0, sizeof(ch[0]));
        memset(dep, 0, sizeof(dep));
        id = 1;
    }
    void Insert(char *s)
    {
        int rt = 0;
        int len = strlen(s);
        dep[rt] = 0;
        for(int i = 0; i < len; i++)
        {
            if(!ch[rt][s[i]-'a'])
            {
                memset(ch[id], 0, sizeof(ch[id]));
                flag[id] = 0;
                ch[rt][s[i]-'a'] = id++;
            }
            dep[ch[rt][s[i]-'a']] = dep[rt] + 1;
            rt = ch[rt][s[i]-'a'];
        }
    }
    void get_fail()
    {
        queue<int> q;
        fail[0] = 0;
        int rt = 0;
        for(int i = 0; i < 26; i++)
        {
            rt = ch[0][i];
            if(rt)
            {
                q.push(rt);
                fail[rt] = 0;
            }
        }
        while(!q.empty())
        {
            int r = q.front();
            q.pop();
            for(int i = 0; i < 26; i++)
            {
                rt = ch[r][i];
                if(!rt)
                {
                    ch[r][i] = ch[fail[r]][i];
                    continue;
                }
                q.push(rt);
                fail[ch[r][i]] = ch[fail[r]][i];
            }
        }
    }
    void Match(char *s, int f)
    {
        int rt = 0;
        int len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int temp = rt = ch[rt][s[i]-'a'];
            while(temp)
            {
                flag[temp] = f;
                temp = fail[temp];
            }
        }
    }
    int Search(char *s, int f)
    {
        int rt = 0, res = 0;
        int len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int temp = rt = ch[rt][s[i]-'a'];
            while(temp)
            {
                if(flag[temp] == f) res = max(res, dep[temp]);
                temp = fail[temp];
            }
        }
        return res;
    }
}ac_auto;
char s[maxn];
int main()
{
    int t, q;
    cin >> t;
    while(t--)
    {
        scanf("%d", &n);
        int d = 0;
        ac_auto.init();
        for(int i = 0; i < n; i++)
        {
            pos[i] = d;
            scanf(" %s", s+d);
            ac_auto.Insert(s+d);
            int len = strlen(s+d);
            d += len + 1;
        }
        ac_auto.get_fail();
        scanf("%d", &q);
        int ca = 1;
        while(q--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            x--; y--;
            ac_auto.Match(s+pos[x],ca);
            int ans = ac_auto.Search(s+pos[y], ca++);
            printf("%d\n", ans);
        }
    }
    return 0;
}