题意简述
请你在一个字符串$S$中找到最大的$k$,使得存在长度为$k$的前缀,后缀和子串,三者没有一点交集,且字符串值相等。算法必须线性(数据水,网上会被卡成n^2的算法也过了)(这是全网为数不多几个严格线性的题解)
思路框架
建一颗$fail$树。然后用树上操作解决问题。
具体思路
我们用$KMP$中的$fail$数组建一颗树,从$i$到$fail_i$连一条边。不难发现,$0$就是根节点。
然后,我们先解决问题的几个部分解决。
前缀=后缀
前缀等于后缀并且位置不相等(即:长度不是n)。那满足条件的长度一定在$n$号节点(不含)到根节点(含)的路径上。我们知道,$S$中满足前缀=后缀的长度就是fail[n],fail[fail[n]]…0。也就是从$n$到根的路径了。
前缀=某个子串
然后我们要找到一个子串和它们相等。($S$的)子串,就是(某个)前缀的(某个)后缀。而(某个)前缀的(某个)前缀还是($S$的)前缀。
所以,如果$S$的一个以$i$结尾的子串和$S$的某个前缀相等,这个长度一定在$i$到根的路径上。
合并
那么我们发现三者相等。所以,这个要求的长度,即在$i$到根的路径上,也在$n$到根的路径上。那么它就在$i$和$n$的$LCA$到根的路径上。
稍微一想,长度最长,就是$LCA$最深。我们要求$LCA$最深,有这样一个方法:给每个点一个点权,初始为$0$。然后从$n$到$1$的路径上都加上$1$。对于每个$i$,我们询问$i$到根路径上点权的和,就是$i$和$n$的$LCA$的深度。然后我们只需要维护一个树上前缀和,然后找到前缀和最大的位置即珂。
别忘了三者不能有相交
那咋整嘛。首先,前缀,后缀还有子串不能相交,那么长度就小于等于n的三分之一。由于我们我们在用上面的方法给点权+1的时候,判一下这个点的编号是否小于n的三分之一,如果满足,那才+1。
然后我们找到$LCA$之后,不断判断$LCA$的长度是否小于$n$的三分之一,如果小于就跳$fail$。当然,我们在找$LCA$的时候,由于只有一组数据,我们也是一样的找法。用代码写,就是:1
while(LCA上点权为0) 跳fail;
然后$LCA$就是我们要求的最长长度了。记得要判一下无解。
时间复杂度
我们发现,我们刚刚说到了这样几个操作:
- 求字符串的fail
- 树上一条链加值
- 树上求前缀和
这些都是$O(n)$完成的操作。所以我们的算法是严格$O(n)$的,连$log$都不带。
代码: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
using namespace std;
namespace Flandre_Scarlet
{
char s[N];int n;
void Input()
{
scanf("%s",s+1);n=strlen(s+1);
}
int fail[N];
void GetFail()
{
fail[1]=0;
F(i,2,n)
{
int j=fail[i-1];
while(s[j+1]!=s[i] and j) j=fail[j];
if (s[j+1]==s[i]) ++j;
fail[i]=j;
}
}
int val[N],rsum[N];//点权,点权的前缀和
void Soviet()
{
F(i,0,n+5) fail[i]=val[i]=rsum[i]=0;
GetFail();//fail[i]是树上i节点的父亲
int pos=n;
while(pos) {{if (pos*3<=n) val[pos]=1;}pos=fail[pos];} //求出点权
F(i,1,n) rsum[i]=rsum[fail[i]]+val[i];//维护前缀和
int Max=0;
F(i,2,n-1)//注意是2到n-1。当然你也珂以认为是n*1/3到n*2/3
{
if (!val[i]) if (rsum[i]>rsum[Max]) Max=i; //求出最深的LCA
}
if (rsum[Max]==0) {puts("0");return;}//判无解
int LCA=Max;
while(!val[LCA]) LCA=fail[LCA];//这里会死循环吗?
printf("%d\n",LCA);
}
Flan IsMyWife()
{
int t;cin>>t;
while(t--)
{
Input();
Soviet();
}
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();getchar();
return 0;
}
代码中的问题答案:不会,因为显然val[0]=1.