一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的，是指如果文章 $T$ 可以被分成若干部分，且每一个部分都是字典 $D$ 中的单词。
给定一个字典 $D$ ，你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。并给出其在字典 $D$ 下能够被理解的最长前缀的位置。
链接
Luogu P2292
题解
可以想到一个简单的 $\text{dp}$ ，用 $dp[i]$ 表示以 $i$ 为结尾的后缀能否被理解：
$$
dp[i] = \max(dp[i-\text{len} _ j]) ,\text{if} ; \text{str} _ j \text{在 i 位置上出现}
$$
然后用模版串 $\text{AC}$ 自动机跑一遍母串，得到每个模版串在母串中出现的位置，然后刷表 $dp$ 即可。
注意往回不能暴力跳 $fail$ ，一个简单的优化是记录最近的 $\text{end}$ 节点 $g_i$ ，然后每次都按照 $g_i$ 跳，统计出现位置即可。
时间复杂度 $O(n \times \text{玄学})$ 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1000,sigma_size = 26;
vector<int> pos[MAXN];
namespace AC{
int c[MAXN][sigma_size],fail[MAXN],g[MAXN];
int end[MAXN];
int root,cnt,wcnt;
void insert(char *s){
int n = strlen(s),nown = root;
for(int i = 0;i<n;i++){
if(c[nown][s[i]-'a'] == 0){
c[nown][s[i]-'a'] = ++cnt;
}
nown = c[nown][s[i]-'a'];
}
end[nown] = ++wcnt;
}
void build(){
queue<int> q;
for(int i = 0;i<sigma_size;i++){
if(c[root][i]){
fail[c[root][i]] = root;
q.push(c[root][i]);
}
}
while(!q.empty()){
int nown = q.front();q.pop();
for(int i = 0;i<sigma_size;i++){
g[nown] = end[fail[nown]]?fail[nown]:g[fail[nown]];
if(c[nown][i] == 0){
c[nown][i] = c[fail[nown]][i];
}
else{
fail[c[nown][i]] = c[fail[nown]][i];
q.push(c[nown][i]);
}
}
}
}
void query(char *s){
for(int i = 1;i<=20;i++){
pos[i].clear();
}
int n = strlen(s),nown = root;
for(int i = 0;i<n;i++){
nown = c[nown][s[i] - 'a'];
for(int t = nown;t;t = g[t]){
if(end[t]){
pos[end[t]].push_back(i);
}
}
}
}
}
int n,m;
int now[MAXN],l[MAXN];
char s[1100000];
bool dp[1100000];
int cal(char *s){
memset(now,0,sizeof(now));
memset(dp,0,sizeof(dp));//dp -> len
int len = strlen(s),ans = 0;
AC::query(s);
dp[0] = 1;
for(int i = 1;i<=len;i++){
for(int j = 1;j <= n;j++){
if(now[j] != pos[j].size() && pos[j][now[j]] == (i-1)){
dp[i] |= dp[i-l[j]];
now[j] ++;
}
if(dp[i] == 1){
ans = max(ans,i);
continue;
}
}
}
return ans;
}
void init(){
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%s",s);
l[i] = strlen(s);
AC::insert(s);
}
AC::build();
}
void solve(){
for(int i = 1;i<=m;i++){
scanf("%s",s);
printf("%d\n",cal(s));
}
}
int main(){
init();
solve();
return 0;
}
|
