題面
思路
水法
不應(yīng)該說是水法吧，只是考試的時(shí)候可能想不到別的了仰猖。
利用了數(shù)據(jù)隨機(jī)性捏肢。對(duì)所有的S_i建立字典樹，并記錄字典樹上每個(gè)點(diǎn)被哪些S_i經(jīng)過了饥侵，這個(gè)可以用vector實(shí)現(xiàn)鸵赫。
對(duì)于每次詢問，在字典樹上跑到對(duì)應(yīng)的節(jié)點(diǎn)（沒有節(jié)點(diǎn)可跑說明T_i不是任何S_i的前綴躏升，此時(shí)答案就是n）辩棒，然后暴力遍歷這個(gè)節(jié)點(diǎn)的vector求出答案。
復(fù)雜度最差是O(nm)膨疏，由于數(shù)據(jù)的隨機(jī)性一睁，就可以過掉。
（去你***的水法佃却，憑什么滿分）
基于水法優(yōu)化的正解
上面做法的瓶頸在于必須用vector存下所經(jīng)過的S_i集合者吁。但是有必要全部存下來嗎？
題目要求的是數(shù)組a里的最長(zhǎng)連續(xù)0饲帅，其實(shí)我們可以將問題轉(zhuǎn)化一下：求相鄰的1的差值-1的最大值复凳，和n-最后一個(gè)1所在位置之差取一個(gè)max瘤泪。
由于字符串是按照編號(hào)順序插入的，我們每次在集合里添加的編號(hào)都和上一個(gè)添加的編號(hào)是相鄰的染坯，因此對(duì)于字典樹上的節(jié)點(diǎn)記錄兩個(gè)信息均芽，就可以避免存下整個(gè)集合，這兩個(gè)信息分別是：
last[i]表示節(jié)點(diǎn)i上一次被編號(hào)last[i]的字符串經(jīng)過单鹿。
ans[i]表示節(jié)點(diǎn)i的答案。
復(fù)雜度就是字符串總長(zhǎng)深纲，與輸入同階仲锄。
Code：
#include <cstdio>
#include <cstring>
#include <cstdlib>
inline int max(int a, int b) { return a > b ? a : b; }
const int LEN = 5e6 + 7;
int n, m, len;
int root, tot, son[LEN][3], mx[LEN], ans[LEN];
char str[LEN];
void insert(int ind)
{
int now = root;
for (int i = 1; i <= len; i++)
{
if (!son[now][str[i] - 'a']) son[now][str[i] - 'a'] = ++tot;
now = son[now][str[i] - 'a'];
ans[now] = max(ans[now], ind - mx[now] - 1);
mx[now] = max(mx[now], ind);
}
}
int getans()
{
int now = root;
for (int i = 1; i <= len; i++)
{
if (!son[now][str[i] - 'a']) return n;
now = son[now][str[i] - 'a'];
}
if (mx[now] == n) return ans[now];
else return max(ans[now], n - mx[now]);
}
int main()
{
freopen("word.in", "r", stdin);
freopen("word.out", "w", stdout);
root = ++tot;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", str + 1), len = strlen(str + 1), insert(i);
for (int i = 1; i <= m; i++) scanf("%s", str + 1), len = strlen(str + 1), printf("%d\n", getans());
fclose(stdin);
fclose(stdout);
return 0;
}
