真是一道好题喵~
果然自动机什么的就是要和 dp 搞基才是王道有木有！
A:连 CTSC 都叫我们搞基，果然身为一个程序猿，加入 FFF 团是我此生最明智的选择。妹子什么闪边去，大家一起来搞基吧！
Q:教练你是什么时候产生了 dp 和自动机是同性的错觉~ 教练你又是什么时候产生了你还有个不入团的选择 ( 妹 子 )这样的错觉~
A:显而易见的，我们……
Q:教练不要转移话题啊！
A:显而易见的，我们先搞一个后缀自动机……
Q:等等，教练，多串的自动机要怎么写？
A:把几个串并在一起不就好了？
Q:不对啊，那查询的时候万一查到两个串相连的地方，不是悲剧了？
A:你傻啊！搞个分割符什么的不就解决了？！
Q:教练我的分割符是用 $ 还是用 # 呢？
(旁白:当然是 $ 了，$ 可是美金的意思，# 算什么，电话号码吗？)
A:。。。。。。
搞出了后缀自动机，就像我们经常做的一样，把每个节点能匹配的最长长度搞出来 (Q:我没文化你也不能这么逗我！)
把字串 S 在第 i 位能匹配到的最长长度 same[i] 搞出来
考虑二分答案L
就有了个显而易见的 dp 转移方程:
f[i]=max{f[j]-j+i | i-same[i]<=j<=i-L}
然后题目就被妥妥的解决了
Q:不对啊教练，这 dp 是 O(n2) 的！
f[i]=max{f[j]-j+i | i-same[i]<=j<=i-L} ↔ f[i]-i=max{f[j]-j | i-same[i]<=j<=i-L}
A:这显然是单调的，优化优化就 O(n) 了
Q:教练求证明……
A:这个显然嘛，显然……要不然这题还怎么做额？
Q:教练……
A:烦死了，你打个表不就行了！
#include <cstdio>
#include <cstring>
#include <cmath>
const int sizeOfType=;
const int sizeOfString=;
const int sizeOfMemory=; inline void getstring(char * s)
{
register char ch;
register int top=;
do ch=getchar(); while (ch<'' || ch>'');
do s[top++]=ch, ch=getchar(); while (ch>='' && ch<='');
s[top]='\0';
} struct deque
{
int l, r;
int q[sizeOfString];
inline deque():l(), r(-) {}
inline void clear() {l=, r=-;}
inline bool empty() {return l>r;}
inline int front() {return q[l];}
inline int back() {return q[r];}
inline void push(int x) {q[++r]=x;}
inline void pop_front() {++l;}
inline void pop_back() {r--;}
}; int N, M;
int len;
int same[sizeOfString];
char str[sizeOfString];
deque q;
int f[sizeOfString], g[sizeOfString];
inline int max(int x, int y) {return x>y?x:y;}
inline void dp(int); namespace suffixAutomaton
{
struct node
{
int step;
node * fail;
node * ch[sizeOfType];
};
node memory[sizeOfMemory], * port=memory;
node * dfa, * last;
inline node * newnode(node * t=NULL)
{
node * newt=port++;
newt->step=;
if (t) newt->fail=t->fail, t->fail=newt, memcpy(newt->ch, t->ch, sizeof t->ch);
else newt->fail=NULL, memset(newt->ch, , sizeof newt->ch);
return newt;
}
inline void clear() {port=memory; dfa=newnode(); dfa->fail=dfa; last=dfa;} inline int ord(char ch) {return ch>=''?ch-'':;}
inline void insert(int w)
{
node * p=last, * newp=newnode();
newp->step=p->step+; for ( ;p->ch[w]==NULL;p=p->fail) p->ch[w]=newp;
if (p->ch[w]==newp)
newp->fail=dfa;
else
{
node * q=p->ch[w];
if (q->step==p->step+)
newp->fail=q;
else
{
node * newq=newnode(q);
newq->step=p->step+;
newp->fail=newq;
for ( ;p->ch[w]==q;p=p->fail) p->ch[w]=newq;
}
} last=newp;
}
inline void buildDfa()
{
static char s[sizeOfString];
int len; clear();
for (int i=;i<M;i++)
{
getstring(s); len=strlen(s);
for (int j=;j<len;j++)
insert(ord(s[j]));
insert(ord('$'));
}
}
inline void search(char * s)
{
int tot=;
node * t=dfa; for (int i=;i<=len;i++)
{
int w=ord(s[i-]);
if (t->ch[w])
{
t=t->ch[w];
++tot;
}
else
{
node * j;
for (j=t->fail;j!=dfa && !j->ch[w];j=j->fail);
if (j->ch[w])
{
t=j->ch[w];
tot=j->step+;
}
else
{
t=dfa;
tot=;
}
}
same[i]=tot;
}
}
} int main()
{
scanf("%d %d", &N, &M);
suffixAutomaton::buildDfa();
for (int i=;i<=N;i++)
{
getstring(str);
len=strlen(str);
suffixAutomaton::search(str); int L=, R=len+;
while (L+<R)
{
int M=(L+R)>>;
dp(M);
if (*f[len]>=*len) L=M;
else R=M;
} printf("%d\n", L);
} return ;
}
inline void dp(int L)
{
q.clear(); for (int i=;i<=len;i++)
{
int j=i-L;
if (j>=)
{
for ( ;!q.empty() && g[j]>g[q.back()];q.pop_back());
q.push(j);
}
f[i]=f[i-];
for ( ;!q.empty() && q.front()<i-same[i];q.pop_front());
if (!q.empty())
f[i]=max(f[i], g[q.front()]+i);
g[i]=f[i]-i;
}
}
本傻乱搞系列
后记:
话说我根本不知道如何证明单调性，但是大家注意到这是类似于一个一直在往右移动的窗口(不要问我为什么 i-same[i] 是单增的，事实如此)
移动的窗口，求窗口中最大的数……很眼熟啊！经验和直觉都告诉我们这就是单调队列……
大家理性理解一下就好，就好~