USACO 2.3.1: Longest Prefix(DP)


题意

洛谷 P1470 最长前缀 Longest Prefix

给定若干个字符串和另一个字符串S,问S的能由上述字符串组成的最长的前缀的长度。

分析

普通的动态规划。刚才好像刚刚在Leetcode上做了一道很相似的题:139. Word Break

一种转移方法是从前转移:对于当前的字符串结尾,枚举所有前缀,找到能够和它匹配的,判断减去匹配部分之后的字符串能否被构成。

另一种转移方法则是向后转移:对于当前(可行的)字符串末尾,枚举所有前缀,找到能够和后面的字符串匹配的,然后记减去前缀后的字符串为可行。这种方法可以利用Trie来进行优化,比前一种更快。

代码

普通的DP

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
/*
ID: zhanghu15
TASK: prefix
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

vector<string> prefix;

bool ok[200000];

int main() {
ofstream fout("prefix.out");
ifstream fin("prefix.in");

string p;
while (fin >> p) {
if (p == ".") break;
prefix.push_back(p);
}

string s;
while (fin >> p)
s += p;

int n = s.length(), m = prefix.size();
int ans = 0;
// ok[i]:以i为结尾的字符串是否可行
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (prefix[j].size() - 1 > i) continue;
if (s.substr(i - prefix[j].size() + 1, prefix[j].size()) != prefix[j])
continue;
if (i == prefix[j].size() - 1 || ok[i - prefix[j].size()]) {
ok[i] = true;
break;
}
}
ans = ok[i] ? i + 1 : ans;
}
fout << ans << endl;
return 0;
}

普通的Trie

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
/*
ID: zhanghu15
TASK: prefix
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

vector<string> prefix;

bool f[200005];

struct TrieNode {
TrieNode* ch[26];
bool isEnd;
TrieNode() {
memset(ch, 0, sizeof(ch));
isEnd = false;
}
};

int main() {
ofstream fout("prefix.out");
ifstream fin("prefix.in");

string pre;
TrieNode* root = new TrieNode();
while (fin >> pre) {
if (pre == ".") break;
prefix.push_back(pre);
TrieNode* p = root;
for (char c: pre) {
if (p->ch[c - 'A'] == NULL)
p->ch[c - 'A'] = new TrieNode();
p = p->ch[c - 'A'];
}
p->isEnd = true;
}

string s, t;
while (fin >> t)
s += t;

int n = s.length();
int ans = 0;
// f[i]:以i结尾的字符串是否可行
for (int i = 0; i < n; i++) {
if (i != 0 && !f[i - 1]) continue;
TrieNode* p = root;
for (int j = i; j < n; j++) {
p = p->ch[s[j] - 'A'];
if (p == NULL) break;
if (p->isEnd) f[j] = true;
}
}
for (int i = 0; i < n; i++)
if (f[i])
ans = max(ans, i + 1);
fout << ans << endl;
return 0;
}

 评论