# [洛谷 2292][HNOI2004] L语言【AC自动机+DP】

• 2018-02-27
• 0
• 0

## Problem:

### 输入输出样例

```4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname
```

```14  （整段文章’whatisyourname’都能被理解）
6  （前缀’whatis’能够被理解）
0  （没有任何前缀能够被理解）```

## Solution:

AC 自动机在询问时会从前到后找到所有出现在文本中的模式串及其位置，同步 DP 并记录最右的匹配点即可，这样就可以将时间复杂度降至 O(mLT) = O(20*106) = O(2*107)，可以 AC。

## Code: O(mLT), 其中LT为文本均长 [4062K, 172MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, m, Plen[22], Tlen;
char P[22][12], T[1050000];
bool dp[1050000];

struct Aho_Corasick_Automaton{
int trie[202][26], fail[202], id[202], cnt[202], topp;
int q[202], fr, re;

inline void insert(char *str, int len, int str_id){
int cur = 0;
for(register int i = 0; i < len; i++){
int v = str[i] - 'a';
if(!trie[cur][v]) trie[cur][v] = ++topp;
cur = trie[cur][v];
}
id[cur] = str_id;  // Only consider one of repeated strings
}

inline void build_fail(){
for(register int i = 0; i < 26; i++) if(trie[0][i]) fail[trie[0][i]] = 0, q[re++] = trie[0][i];
while(fr != re){
int u = q[fr++];
for(register int i = 0; i < 26; i++)
if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], q[re++] = trie[u][i];
else trie[u][i] = trie[fail[u]][i];
}
}

inline int match_dp(char *str, int len){
int cur = 0, mx = 0;
memset(dp, 0, sizeof(dp)), dp[0] = 1;
for(register int i = 1; i <= len; i++){
cur = trie[cur][str[i - 1] - 'a'];
for(register int j = cur; j; j = fail[j])
if(id[j] && dp[i - Plen[id[j]]]) dp[i] = 1, mx = i;
}
return mx;
}
} AC;

int main(){
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i++) scanf("%s", P[i]), Plen[i] = strlen(P[i]), AC.insert(P[i], Plen[i], i);
AC.build_fail();
for(register int i = 1; i <= m; i++){
scanf("%s", T), Tlen = strlen(T);
printf("%d\n", AC.match_dp(T, Tlen));
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai