[BZOJ1212] [HNOI2004]L 언어(AC 로봇 + dp)

제목 설명

전송문

문제풀이

이 문제는 처음부터 폭력이 생각났지만 시간 복잡도는 O(20 ∗ 10 ∗ 1M) ≈2 ∗ 108이라고 계산하면 분명 과학적이지 않다.그런데 인터넷에서 문제풀이를 찾아보니까 다들 폭력적인 방법을 쓰는 것 같았어요. 그리고 20*10*1M이 가볍게 지나갔다고 하는데 왜 1M이 10242가 아닌지 모르겠어요.
pp의 사고방식이 매우 좋다. 바로 f(i)는 앞의 i개가 합법적인 꼬치인지 아닌지를 나타낸다. 만약에 위치 i에서 어떤 접미사를 빼면 합법적인 f(i)가 반드시 합법적이라는 것을 알 수 있다. 그러면 AC자동기 폭력 매칭 폭력 매칭 폭력 매칭을 구축하면 된다.한 번의 일치 시간은 1M이고 나무의 깊이는 10이기 때문에 전체 시간의 복잡도는 O(20°10°1M)이다.

코드

#include
#include
#include
#include
using namespace std;
#define N 205
#define S 1100000

char s[S];
int n,m,len,sz;
bool f[S];
int ch[N][30],fail[N],is_end[N];
queue <int> q;

void insert()
{
    int len=strlen(s),now=0;
    for (int i=0;iint x=s[i]-'a';
        if (!ch[now][x]) ch[now][x]=++sz;
        now=ch[now][x];
    }
    is_end[now]=len;
}
void make_fail()
{
    while (!q.empty()) q.pop();
    for (int i=0;i<26;++i)
        if (ch[0][i]) q.push(ch[0][i]);
    while (!q.empty())
    {
        int now=q.front();q.pop();
        for (int i=0;i<26;++i)
        {
            if (!ch[now][i])
            {
                ch[now][i]=ch[fail[now]][i];
                continue;
            }
            fail[ch[now][i]]=ch[fail[now]][i];
            q.push(ch[now][i]);
        }
    }
}
void ac()
{
    int now=0;
    for (int i=0;iint x=s[i]-'a';
        int y=ch[now][x];
        while (y)
        {
            f[i+1]|=f[i+1-is_end[y]];
            y=fail[y];
        }
        now=ch[now][x];
    }
}
int main()
{
    scanf("%d%d
",&n,&m);
    for (int i=1;i<=n;++i)
    {
        gets(s);
        insert();
    }
    make_fail();
    for (int i=1;i<=m;++i)
    {
        gets(s);len=strlen(s);
        memset(f,0,sizeof(f));f[0]=1;
        ac();
        for (int i=len;i>=0;--i)
            if (f[i])
            {
                printf("%d
",i);
                break;
            }
    }
}