题目传送门(BZOJ)
>原文链接<

题解 :

由于只有20个词,我们暴力哈希都可以

先对单词建立AC自动机,危险节点标记是单词长度。

状态

F[i]表示在当前模式串上匹配到第i个字符的可行性。

转移

若跳到i是危险节点,那么就从这个危险节点开始跳fail,F[i] |= F[i-flag[j]], j = fail[j],不断更新即可。

否则在Trie图上从当前点跳一下s[i+1]即可。

答案

ans就是最大的i满足F[i] = 1 ,初始状态F[0] = 1

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 210;bool f[1001000];char s[1001000];struct AC_Automaton { int ch[N][26], fail[N], cnt, flg[N]; queue<int> q; inline void insert() { int p = 0, len = strlen(s+1); for(int i = 1; s[i]; i ++ ) { int &k = ch[p][s[i]-'a']; if(!k) k = ++cnt; p = k; } flg[p] = len; } void getFail() { for(int i = 0; i < 26; i ++ ) if(ch[0][i]) q.push(ch[0][i]); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 0; i < 26; i ++ ) { if(ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]); else ch[u][i] = ch[fail[u]][i]; } } } void match() { int p = 1, ans = 0; for(int i = 1; s[i]; i ++ ) { p = ch[p][s[i]-'a']; for(int j = p; j; j = fail[j]) if(flg[j]) { f[i]|=f[i-flg[j]]; if(f[i]) {ans = i; break;} } } printf("%d\n", ans); }}Trie;int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) { scanf("%s", s+1); Trie.insert(); } Trie.getFail(); while(m -- ) { memset(f, 0, sizeof f); f[0] = 1; scanf("%s", s+1); Trie.match(); }}