洛谷 P2292 [HNOI2004]L语言
- 作者: 执丶落
- 来源: 51数据库
- 2021-07-08
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;
}
推荐阅读