符号规定
先来规定一些符号。
- (lvert Srvert) 代表这个字符串 (S) 的长度。
- (S_{lcdots r}) 代表字符串从第 (l) 个字符到第 (r) 个字符组成的字串。
- (F(S,i)) 等同于 (S_{1cdots i})(就是字符串长度为 (i) 的前缀)
- (E(S,i)) 等同于 (S_{lvert Srvert-i+1cdots lvert Srvert}) (就是字符串长度为 (i) 的后缀)注意在我们的定义里这个后缀是从左往右读的
- (B(S)) 表示 (S) 的一个最长 border 的长度(具体什么是 border 之后再谈)
前置芝士—border
定义
如果一个字符串 (S) 存在一个长度为 (x) 的 border,则有 (F(S,x)=E(S,x))。也就是一个字符串的长度为 (x) 的前缀与长度为 (x) 的后缀相等。
例子
对于这个字符串:
]
它的border有:
]
]
与
]
]
特别的,我们为了方便一般不认为一个完整的字符串是 border。
求法
对于一个字符串 (S),我们一般会记录最大 border。我们只要能求出来最大 border 就可以求出所有的 border。这是因为border 是存在包含关系的。就比如上一个例子的第二个 border 实际上是基于第一个 border 的。
那我们考虑求法。设 (pi_i) 代表 (B(F(S,i))),即 (S) 的长度为 (i) 的前缀的最长 border。
KMP 发现 (pi) 是可以被递推的。
我们目前假设知道了 (pi_{1cdots i}),现在要求 (pi_{i+1})。
有一个结论:(pi_{i+1}) 一定是 (pi_{1cdots i}) 中的一个 (+1)。因为它只有前面是 border 了之后才能拼上。
那么我们不妨设一个 (f(x,c)) 代表目前 (F(S,x)) 是一个 border 的前缀,然后我们考虑它所属的 border 能否匹配上 (c) 这个字符。
我们先给出 (f) 的递归逻辑,之后再解释。
left{
begin{array}{l}
x+1 spacespacespace(S_{x+1}=c)\
0spacespacespacespacespacespacespacespacespacespace(x=0)\
f(pi_x,c)\
end{array}
right.
]
]
首先解释最简单的 (0),这是因为如果当前能匹配的已经没有了,然后上面那个能够匹配的东西又不符合,所以就没有更小的原来的 border 用来匹配了。所以就返回 (0)。
然后的话我们先来从一开始看一下一幅图:
这就是我们的初始状态。因为 border 的性质两个绿色部分是完全一样的,所以我们一开始判断的就是黄色是否等于蓝色,如果是的话显然这就是一个新的 border,然后因为 (pi_{i-1}) 就是之前最长的了,所以显然满足 (pi_i) 性质,直接更新。
否则的话我们根据递归就是判断下面这幅图:
这个时候很神奇的事情就发生了,根据 border 性质,四个紫色部分显然是一样的,那么还是判断黄色和蓝色的就行了。因为一定有一个紫色在开头,还有一个紧挨着蓝色。然后紫色也一定是最长的次大,所以在绿色不满足性质的情况下它仍然是满足 (pi) 的性质的。然后就愉快的求完了。
KMP
KMP 算法是一种用 (O(lvert Srvert)) 的时间复杂度来求出模式串 (T) 在文本串 (S) 中的所有出现位置的算法。
算法流程
我们先对于 (T) 求出 (pi),也就是知道了所有的 (B(F(T,i)))。
然后开始匹配。我们首先枚举 (S_i),并记录 (l) 满足 (T_{1cdots l}=S_{i-l+1cdots i})。显然如果 (l=lvert Trvert) 则 (S_{i-l+1cdots i}=T),也就是匹配成功一次。那么关键在于我们怎么线性维护这个 (l)。
先说结论:直接让 (l=f(l,S_i)) 即可。
对于这样一幅图,你会发现它就是答案。首先合法性肯定可以理解,因为每一个相同颜色的部分根据 border 性质显然是一样的,不过多解释。至于最优性,你会考虑深蓝色部分为什么不可以再延伸,这是因为如果可以再向左延伸,又因为 (S) 需要包含前面的,则 border 也会变得更长,不符合 (f) 的定义,矛盾。所以直接这么求即可。
例题
P3375 【模板】KMP
题目大意
给出两个字符串 (s_1) 和 (s_2),若 (s_1) 的区间 ([l, r]) 子串与 (s_2) 完全相同,则称 (s_2) 在 (s_1) 中出现了,其出现位置为 (l)。
现在请你求出 (s_2) 在 (s_1) 中所有出现的位置。
(1 leq |s_1|,|s_2| leq 10^6),(s_1, s_2) 中均只含大写英文字母。
解法
kmp 模版,参考上方解法。
代码
#include
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
string s,t;
ll n,m;
ll pi[MAXN];
ll find_next(ll ed,char need) {
if(t[ed+1]==need) {
return ed+1;
}
return ed==0?0:find_next(pi[ed],need);
}
void kmp() {
for (int i=2;i>s>>t;
n=s.size(),m=t.size();
s=" "+s;
t=" "+t;
kmp();
find();
for (int i=1;i
CF126B Password
题目大意
给出字符串 (S),你需要找到既是 (S) 的前缀又是 (S) 的后缀同时又在 (S) 中间出现过的最长子串。
(1leq lvert Srvert leq 10^6)
解法
首先显然要求出来关于 (S) 的 border 数组 (pi)。
然后我们如果要求出 (S) 的所有 border 的话只需要不断求 (Large{pi_{pi_{cdots_{pi_{lvert Srvert}}}}})。因为 border 存在包含关系。
之后我们只要判断这个子串是否在中间出现过就行了。如果 (S) 中出现过一个长度为 (k) 的 border 则 (existspi_i=k,iin[2,lvert Srvert-1])。所以我们求 (m=max(pi_i),iin[2,lvert Srvert-1])。然后我们一直迭代 (S) 的 border 直到当前的长度 小于 (m) 就停。因为存在包含关系所以一定可以。那么把这个 border 输出即可。
代码
#include
#define endl 'n'
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
string s,t;
ll n,m;
ll pi[MAXN];
ll find_next(ll ed,char need){
if(t[ed+1]==need){
return ed+1;
}
return ed==0?0:find_next(pi[ed],need);
}
ll ans;
void kmp(){
for(int i=2;i>t;
m=t.size();
t=" "+t;
kmp();
ll ma=0;
for(int i=1;ima){
ans=pi[ans];
}
if(ans==0){
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net