FZU2128_最长子串

题目说给你一个长串，要你选一个最长子串，不包括任何一个给定串为子串。

建立一个自动机，每个点保存的信息为当前这个状态为结尾最长可以有多长？

然后。。。。就可以了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 1000100
#define inf 99999999
using namespace std;char s0[maxn];
char s[];
int next[][],fail[],tag[],N;
int n,m,f[maxn],ans;int add()
{
    N++;
    for (int i=; i<; i++) next[N][i]=;
    tag[N]=inf;
    fail[N]=;
    return N;
}void init()
{
    N=-;
    N=add();
}void insert()
{
    int cur=,tep;
    for (int i=; s[i]; i++)
    {
        tep=s[i]-'a';
        if (next[cur][tep]==) next[cur][tep]=add();
        cur=next[cur][tep];
    }
    tag[cur]=strlen(s);
}void AC_build()
{
    int cur,child;
    queue<int> Q;
    Q.push();
    while (!Q.empty())
    {
        cur=Q.front(),Q.pop();
        for (int i=; i<; i++)
        {
            child=next[cur][i];
            if (child)
            {
                Q.push(child);
                if (cur==) fail[child]=;
                else fail[child]=next[fail[cur]][i];
                tag[child]=min(tag[child],tag[fail[child]]);
            }
            else next[cur][i]=next[fail[cur]][i];
        }
    }
}void query()
{
    ans=;
    f[]=;
    int cur=,tep;
    for (int i=; s0[i]; i++)
    {
        f[i]=f[i-]+;
        tep=s0[i]-'a';
        cur=next[cur][tep];
        f[i]=min(f[i],tag[cur]);
        ans=max(ans,f[i]);
    }
}int main()
{
    while (scanf("%s",s0+)!=EOF)
    {
        init();
        scanf("%d",&n);
        while (n--)
        {
            scanf("%s",s);
            insert();
        }
        AC_build();
        query();
        printf("%d\n",ans-);
    }
    return ;
}