KMP & 二分 解决 P3426 SZA-Template
__Cielo__
·
·
题解
KMP & 二分 解决 P3426 SZA-Template
前言
最近学二分学魔怔了，看到
## 观察
首先,题目要求“**印章**”（即**模式串**）必须能**刚好盖完文本**（即**主串**）。
我们很容易了解到，**模式串**必须是**主串**的**前后缀**。
于是我就联想到了 **KMP** 中的 **Border**。
## 算法运用 - KMP
很明显，由于**模式串**必须是**主串**的**前后缀**，所以**模式串**可以是**主串**（最坏情况），也可以是**主串**的 **Border** ，还可以是**主串**的 **Border** 的 **Border**……~~（晕）~~
以此类推，我们可以得到**不大于** $n$ **个**的**可能的模式串**。
如下图
```cpp
ababbababbabababbabababbababbaba|
ababbababbaba|bab...
ababbaba|bba...
aba|bba...
a|bab...
```
我们利用 **KMP** 中的 **next** 数组将这些**可能的模式串**求出并存储。
*Code*:
```cpp
for(int i=2,j=0;i<=n;i++)
{
while(a[i]!=a[j+1]&&j)j=ne[j];
j+=(a[i]==a[j+1]),ne[i]=j;
}
for(int i=n;i;i=ne[i])
num[++sum]=i;
```
## 暴力 - 85分
那么，我们就有一个简单的思路，**从小到大**依次**枚举**每一个**可能的模式串**，$\operatorname{check}$ 是否能完全覆盖主串，此时**第一个**满足的就是答案。
*Code*:
```cpp
#include<iostream>
#define N 500005
using namespace std;
string a;
int n;
int f,last;
int num[N],sum;
int ne[N];
bool check(int x)
{
last=0;
for(int i=1,j=0;i<=n;i++)
{
if(i-last>x)
return 0;
while(a[i]!=a[j+1]&&j)j=ne[j];
j+=(a[i]==a[j+1]);
j==x?(last=i,j=ne[j]):0;
}
return 1;
}
int main()
{
cin>>a;
n=a.size();
a=" "+a;
for(int i=2,j=0;i<=n;i++)
{
while(a[i]!=a[j+1]&&j)j=ne[j];
j+=(a[i]==a[j+1]),ne[i]=j;
}
for(int i=n;i;i=ne[i])
num[++sum]=i;
for(int i=sum;i>=1;i--)
if(check(num[i]))
{
cout<<num[i];
return 0;
}
}
```
在**最坏情况**下，这个算法的**时间复杂度**为 $O(n^2)$，而题目条件给出的 $n$ 的**数据范围**为 $n\le5*10^5$，所以会 **TLE**。
## 优化 - 二分
我们观察每个**可能模式串**之间的**联系**，容易发现：**如果主串的** $n$ **次** **Border** **无法通过** $\operatorname{check}$，**那么主串的** $n+1$ **次** **Border** **也无法通过** $\operatorname{check}$。
也就是说，**可能模式串** $\operatorname{check}$ 的结果**满足单调性**。
同时，$n\le5\times10^5$ 的**数据范围**符合 $O(n\log{n})$ 的**时间复杂度**。
我们就可以愉快的~~麻木的~~**二分**了。
最后加入一些**最坏情况**（最优模式串为主串）的特判就能通过了。
*Code*:
```cpp
#include<iostream>
#define N 500005
using namespace std;
string a;
int n;
int f,last;
int num[N],sum;
int ne[N];
bool check(int x)
{
last=0;
for(int i=1,j=0;i<=n;i++)
{
if(i-last>x)
return 0;
while(a[i]!=a[j+1]&&j)j=ne[j];
j+=(a[i]==a[j+1]);
j==x?(last=i,j=ne[j]):0;
}
return 1;
}
int find()
{
int l=1,r=sum,mid;
while(l<r)
{
mid=l+r+1>>1;
if(check(num[mid]))l=mid;
else r=mid-1;
}
return l;
}
int main()
{
cin>>a;
n=a.size();
a=" "+a;
for(int i=2,j=0;i<=n;i++)
{
while(a[i]!=a[j+1]&&j)j=ne[j];
j+=(a[i]==a[j+1]),ne[i]=j;
}
if(!ne[n])
{
cout<<n;
return 0;
}
for(int i=ne[n];i;i=ne[i])
num[++sum]=i;
f=find();
if(check(num[f]))
cout<<num[f];
else
cout<<n;
}
```
## 结
**蒟蒻码字不易，不喜勿喷。**
**最后附上**[**文章链接**](https://www.luogu.com.cn/article/9a36etgv)