AK-dream

【题目描述】
标点符号的出现晚于文字的出现,所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。 我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的,是指如果文章 $T$ 可以被分成若干部分,且每一个部分都是字典 $D$ 中的单词。

例如字典 $D$ 中包括单词 is , your , what , name ,则文章 whatisyourname 是在字典 $D$ 下可以被理解的,因为它可以分成 4 个单词: what , is , your , name ,且每个单词都属于字典 $D$,而文章 whatisyouname 在字典 $D$ 下不能被理解,但可以在字典 D’=D+D’=D+you 下被理解。这段文章的一个前缀 whatis ,也可以在字典 $D$ 下被理解,而且是在字典 $D$ 下能够被理解的最长的前缀。

给定一个字典 $D$ ,你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。 并给出其在字典 $D$ 下能够被理解的最长前缀的位置。

【输入格式】
输入文件第一行是两个正整数 $n$ 和 $m$,表示字典 $D$ 中有 $n$ 个单词,且有 $m$ 段文章需要被处理。

之后的 $n$ 行每行描述一个单词,再之后的 $m$ 行每行描述一段文章。

【输出格式】
对于输入的每一段文章,你需要输出这段文章在字典 $D$ 可以被理解的最长前缀的位置。

题解

朴素想法就是在Trie上一直尽量向下匹配,然后失配了就从失配的地方开始重新从根匹配,然而这个错了

反例很好找

1
2
3
4
5
3 1
road
you
your
youroad

这样暴力匹配的话到了your会失配 然后并没有与oad匹配的词
但是youroad应该是能被全部理解的

所以我们发现对于每个能成功匹配的前缀,都要从它后面开始搜一次
这个例子中前缀1~3及1~4都是能匹配上的 如果从1~3后面 即4开始搜的话就能全部匹配

所以记录一个ok数组 $ok[i]$表示$1\sim i$的前缀能成功匹配

时间复杂度$O(玄学)$ 蒟蒻不会分析

【代码】

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
#include <bits/stdc++.h>
using namespace std;

char s[1000005];
int n, m, tr[10005][30], tag[10005], tot, len;
bool ok[1000005];

inline void insert(char *str, int l) {
int now = 0;
for (int i = 1; i <= l; i++) {
if (!tr[now][str[i]-'a']) tr[now][str[i]-'a'] = ++tot;
now = tr[now][str[i]-'a'];
}
tag[now] = 1;
}

inline void query(char *str, int st, int l) {
int now = 0;
for (int i = st; i <= l; i++) {
if (!tr[now][str[i]-'a']) break;
now = tr[now][str[i]-'a'];
if (tag[now]) ok[i] = 1;
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s+1); len = strlen(s+1);
insert(s, len);
}
for (int i = 1; i <= m; i++) {
memset(ok, 0, sizeof(ok)); ok[0] = 1;
scanf("%s", s+1); len = strlen(s+1);
for (int j = 1; j <= len; j++) {
if (ok[j-1]) query(s, j, len);
}
for (int j = len; j >= 0; j--) {
if (ok[j]) {
printf("%d\n", j); break;
}
}
}
return 0;
}


 评论