import java.util.*;
class Trie {
boolean isEnd;
Trie[] next;
Trie() {
this.next = new Trie[26];
}
}
class Main {
static String s;
static int m, len;
static Trie root;
static boolean[] vt;
public static boolean check(String p, int n) {
for (int i = 0; i < n; ++ i) {
if (p.charAt(i) < 'A' || p.charAt(i) > 'Z') return false;
}
return true;
}
public static void insert(Trie tr, String p, int i, int n) {
if (i == n) {
tr.isEnd = true;
return;
}
int idx = p.charAt(i) - 'A';
if (tr.next[idx] == null) tr.next[idx] = new Trie();
insert(tr.next[idx], p, i + 1, n);
}
public static void dfs(Trie tr, int i) {
if (len == m || tr == null) return;
if (tr == root) {
if (vt[i]) return;
vt[i] = true;
}
if (tr.isEnd) {
len = Math.max(len, i);
dfs(root, i);
}
if (i == m) return;
int idx = s.charAt(i) - 'A';
dfs(tr.next[idx], i + 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
root = new Trie();
while (true) {
String p = sc.next();
if (p.equals(".")) break;
int n = p.length();
if (check(p, n)) insert(root, p, 0, n);
}
s = sc.next();
while (sc.hasNext()) s += sc.next();
m = s.length();
vt = new boolean[m + 1];
dfs(root, 0);
System.out.println(len);
}
}
下面是看了题解写的dp
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Set<String> set = new HashSet<>();
while (true) {
String p = sc.next();
if (p.equals(".")) break;
int n = p.length();
set.add(p);
}
String s = " " + sc.next();
while (sc.hasNext()) s += sc.next();
int m = s.length();
boolean[] dp = new boolean[m + 1];
dp[0] = true;
int ans = 0;
for (int i = 1; i < m; ++ i) {
for (int j = Math.max(0, i - 10); j < i && !dp[i]; ++ j) {
if (set.contains(s.substring(j + 1, i + 1))) dp[i] = dp[j];
}
if (dp[i]) ans = i;
}
System.out.println(ans);
}
}