洛谷 P2292 [HNOI2004]L语言

AC自动机 + dp：
洛谷这题数据加强之后用bfs T了最后一两个点
用了一个dp数组做转移
注意一下字符串下标的偏移（因为有了dp数组）
存下Trie树上的结尾结点的字符串长度
注意一下ac自动机的空间和dp数组的空间
其他就没啥了

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define PI acos(-1)
#define pb(x)   push_back(x)
#define il inline
#define re register
#define IO; ios::sync_with_stdio(0);cin.tie(0);
#define ls (o<<1)
#define rs (o<<1|1)
#define pii pair<int,int>
using namespace std;
const int maxn = 2e6+5;
const int maxm = 1e5+5;
const int INF = 0x3f3f3f3f;
const ll LINF = 3e17+1;
const int mod = 1e9+7;
int n, r,h;
inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}
struct Tree
{
    int fail;
    int vis[27];
    int end;
}Aho[205];
int Len[205], idx;
char t[maxn];
bool dp[maxn];
il void insert(char s[])
{
    int len = strlen(s+1);
    int now = 0;
    for (int i = 1; i <= len; i++)
    {
        int ch = s[i] - 'a' + 1;
        if (Aho[now].vis[ch] == 0)
            Aho[now].vis[ch] = ++idx;
        now = Aho[now].vis[ch];
    }
    Aho[now].end ++;
    Len[now] = len;
}
void get_fail()
{
    queue<int>q;
    for (int i = 1; i <= 26; i++)
    {
        if (Aho[0].vis[i] != 0)
        {
            Aho[Aho[0].vis[i]].fail = 0;
            q.push(Aho[0].vis[i]);
        }
    }
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = 1; i <= 26; i++)
        {
            if (Aho[u].vis[i] != 0)
            {
                Aho[Aho[u].vis[i]].fail = Aho[Aho[u].fail].vis[i];
                q.push(Aho[u].vis[i]);
            }
            else
                Aho[u].vis[i] = Aho[Aho[u].fail].vis[i];
        }
    }
}
int qry(char s[])
{
    dp[0] = 1;
    int now = 0, ans = 0;
    int len = strlen(s+1);
    for (int i = 1; i <= len; i++)
    {
        int ch = s[i] - 'a'+1;
        now = Aho[now].vis[ch];
        dp[i] = 0;
        for (int t = now; t; t = Aho[t].fail)
        {
            if (Aho[t].end)
            {
                dp[i] |= dp[i-Len[t]];
                if (dp[i])
                {
                    ans = i;
                    break;
                }
            }
        }
    }
    return ans;
}
int main()
{
    int m;
    n = read(), m = read();
    char s[205];
    for (int i = 0; i < n; i++)
    {
        scanf("%s", s+1);
        insert(s);
    }
    get_fail();
    for (int i = 0; i < m; i++)
    {
        scanf("%s", t+1);
        printf("%d\n", qry(t));
    }

    return 0;
}

本文地址：https://blog.csdn.net/weixin_43563956/article/details/107495658