Border性质习题与证明
KMP
第一次接触 \(border\) 都是先从 KMP 开始的吧。
思想在于先对于一个串自匹配以求出 fail 指针（也就是 border） 然后就可以在匹配其他串的时候非常自然的失配转移。在此顺便给出一下 \(border\) 的定义：
Border
字符串的某个能与后缀完全匹配的真前缀（即不为原串的前缀）。
在 KMP 中我们一般关注最长的 \(border\)，然后我们 KMP 中的 fail 实际上就是存储的最长的 \(border\) 的结束的位置（因为是前缀所以可以这样存储）。
发现只有我们当前匹配的位置失配了，我们只需要不停跳 fail 直到下一位匹配即可了（或者匹配不上直接回老家）。因为当我们模式串（用于匹配的串）匹配到第 \(i\) 位，且匹配了文本串（用于被匹配的串） \(j\) 位（从某个位置开始的连续 \(j\) 个）的时候，是用模式串的一个前缀子串进行匹配的，如果此时我们将其 \(border\) 拿过来匹配，可以将其放置于原来匹配的与该前缀对应的后缀的位置，因为是 \(border\) 所以是完全重合的。
所以失配的时候跳 \(border\) 是可以匹配上的。然后我们跳最长的 \(border\)，那么我们就能匹配得尽可能长，就不会遗漏。比如说字符串 \(ababab\)，我们用 \(abab\) 去匹配它。我们很顺利的匹配了前 \(4\) 位，完成一次匹配。我们发现如果我们还有把 \([3,6]\) 位置的字符串匹配上，我们又不能把文本串的指针往回，不然复杂度就起飞了。因此我们跳最长的 \(border\) ，模式串指针直接由于 \(border\) 的性质匹配 \(2\) 位，后面再正常匹配就是对的了。
然后我们发现 KMP 用的实际上是模式串的前缀子串的最长 \(border\) ，我们考虑怎么求这个东西。
首先第一位没有真前缀。\(fail[1]=0\) 。然后发现匹配实际上是将一个串的前缀一步一步往另一个串的前缀的后缀上匹配，这不就是匹配 \(border\) 吗？我们直接对模式串自匹配一次即可。
其实 kmp 本质上是建立了一颗 \(fail\) 树。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
inline bool blank(const char &c){
return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
}
inline void gs(char *s){
char ch=gc();
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {*s++=ch;ch=gc();}
*s=0;
}
inline void gs(std::string &s){
char ch=gc();s+='#';
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {s+=ch;ch=gc();}
}
inline void ps(char *s){
while(*s!=0) pc(*s++);
}
inline void ps(const std::string &s){
for(auto it:s)
if(it!='#') pc(it);
}
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p*=0.1;ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=1e6+3;
char c[N],s[N];
int fail[N];
inline void build(char *a){
int j=0;//第一位不匹配，满足真前缀
int len=strlen(a+1);
for(int i=2;i<=len;++i){
while(j and a[j+1]!=a[i]) j=fail[j];
if(a[j+1]==a[i]) ++j;
fail[i]=j;
}
}
inline void kmp(char *a,char *b){
int j=0,len=strlen(b+1);
int lena=strlen(a+1);
for(int i=1;i<=len;++i){
while(j and a[j+1]!=b[i]) j=fail[j];
if(a[j+1]==b[i]) ++j;
if(j==lena){
printf("%d\n",i-j+1);
j=fail[j];
}
}
}
int main(){
filein(a);fileot(a);
gs(c+1);gs(s+1);
build(s);
kmp(s,c);
int len=strlen(s+1);
for(int i=1;i<=len;++i){
printf("%d ",fail[i]);
}pc('\n');
return 0;
}
扩展KMP
LCP
最长公共前缀。
那么扩展KMP 可以用来干嘛呢？
它可以求出 Z函数，也就是字符串的每个后缀与原串的 LCP。具体地说：\(z[i]\) 表示以 \(i\) 开头的后缀的 LCP。
其实讲得通俗一点就是对于每个点求出以它开始的子串最多能与原串开头匹配几位。
我们维护求出的右端点最右的区间 \([l,r=l+z[l]+1]\) ，然后考虑一个要新求 Z函数的 \(i\) ，怎么利用之前原有的贡献来减少计算。
首先分为两种情况，如果 \(r<i\) ，那么显然这个区间和当前的 \(i\) 没有任何关系，从 \(0\) 开始直接暴力扩展。如果 \(i<=r\) ，那么我们知道 \(s[1,r-l+1]=s[l,r]\) ，对应地，在 \(z[i-l+1]<r-i+1\) 的情况下，也就是扩展不超过右界的前提下， \(z[i-l+1]=z[i]\) 。这是因为我们不能保证 \(r\) 右边的部分仍然与前缀对应。后面的部分我们暴力扩展即可。
然后我们用已经求出 Z函数的串扩展KMP 匹配，这个和自匹配求 Z函数其实是一样的不再赘述。
复杂度证明同 manacher，\(r\) 不断增大，可得复杂度为 \(O(n)\) 。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
inline bool blank(const char &c){
return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
}
inline void gs(char *s){
char ch=gc();
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {*s++=ch;ch=gc();}
*s=0;
}
inline void gs(std::string &s){
char ch=gc();s+='#';
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {s+=ch;ch=gc();}
}
inline void ps(char *s){
while(*s!=0) pc(*s++);
}
inline void ps(const std::string &s){
for(auto it:s)
if(it!='#') pc(it);
}
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p*=0.1;ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=2e7+3;
char c[N],s[N];
int z[N],p[N];
inline void z_function(char *a){
int len=strlen(a+1);
z[1]=len;
int l=0,r=-1;
for(int i=2;i<=len;++i){
if(i<=r) z[i]=std::min(z[i-l+1],r-i+1);
while(i+z[i]<=len and a[1+z[i] ]==a[i+z[i] ])
++z[i];
if(i+z[i]-1>r){
l=i;r=i+z[i]-1;
}
}
ll ans=0;
for(int i=1;i<=len;++i){
//printf("%d ",z[i]);
ans^=(1ll*i*(z[i]+1) );
}
printf("%lld\n",ans);
}
inline void exkmp(char *a,char *b){
int len=strlen(a+1),lenb=strlen(b+1);
int l=0,r=-1;
for(int i=1;i<=len;++i){
if(i<=r) p[i]=std::min(z[i-l+1],r-i+1);
while(i+p[i]<=len and 1+p[i]<=lenb and b[1+p[i] ]==a[i+p[i] ])
++p[i];
if(i+p[i]-1>r){
l=i;r=i+p[i]-1;
}
}
ll ans=0;
for(int i=1;i<=len;++i){
//printf("%d ",p[i]);
ans^=(1ll*i*(p[i]+1) );
}
printf("%lld\n",ans);
}
int main(){
filein(a);fileot(a);
gs(c+1);gs(s+1);
z_function(s);
exkmp(c,s);
return 0;
}
Border相关性质
再次提一嘴定义：字符串的某个能与后缀完全匹配的真前缀（即不为原串的前缀）。
性质1：
\(border(S)=border(S)_{max}+border(border(S)_{max})\)，即一个字符串的最长 \(border\) 加上这个最长 \(border\) 的 \(border\)，可以得到整个字符串所有的 \(border\)。
证明：
要不我们之后简称 \(border\) 为 b 吧。（
我们假设 \(S[1,r]\) 为 \(b(S)_{max}\) ，若记 \(\lvert S\rvert=len\) ，则有 \(S[len-r+1,len]\) 为其对应后缀，那么他们的 \(border\) 除了位置不同外没有区别。因此通过相等 \(border\) 的传递，可得到 \(S[1,r]\) 的 \(border\) 与 \(S[len-r+1,len]\) 的 \(border\) 的对应后缀对应，那么等价于一对 \(b(S)\) 的前后缀。那么所有这种 \(border\) 加上其本身就可以得到所有的 \(b(S)\) 。
应用1：求出某个串的所有 \(border\)。
操作：
我们有了性质1，只需要使用 kmp 求出 \(fail\)，然后从 \(n\) 开始一直跳 \(fail\) 就可以得到原串所有 \(border\)。
提一嘴周期的概念：使得 \(S[i]=S[i+p]\) ，则 \(p\) 为串 \(S\) 的周期。容易得知，对于一个周期 \(p\)，\(p+\lvert b(S)\rvert=\lvert S\rvert\) 。注意一个串能有多个周期，就和一个串能有多个 \(border\) ，那么周期与 \(border\) 相对应。
然后我们称 \(p|n\) 的周期 \(p\) 为整周期。
[POI2006] OKR-Periods of Words
题目大意：给一个字符串，要你求其所有前缀的最大周期之和。
那么我们刚刚才说了周期与 \(border\) 对应，因此我们要求最大周期，只需要找到最小 \(border\) 即可。那么我们对于每个前缀跳 \(fail\) 树即可。发现可以记忆化优化一下 \(fail\) 树，直接连到底端。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
inline bool blank(const char &c){
return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
}
inline void gs(char *s){
char ch=gc();
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {*s++=ch;ch=gc();}
*s=0;
}
inline void gs(std::string &s){
char ch=gc();s+='#';
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {s+=ch;ch=gc();}
}
inline void ps(char *s){
while(*s!=0) pc(*s++);
}
inline void ps(const std::string &s){
for(auto it:s)
if(it!='#') pc(it);
}
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p*=0.1;ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=1e6+3;
int n;
char c[N];
int fail[N];
int main(){
filein(a);fileot(a);
read(n);
gs(c+1);
int j=0;
for(int i=2;i<=n;++i){
while(j and c[j+1]!=c[i]) j=fail[j];
if(c[j+1]==c[i]) ++j;
fail[i]=j;
}
ll ans=0;
for(int i=1;i<=n;++i){
int j=i;
while(fail[j]) j=fail[j];
if(fail[i]) fail[i]=j;
ans+=(i-j);
}
printf("%lld\n",ans);
return 0;
}
题目大意：求出每个前缀的不超过 \(\lfloor\frac{len}{2}\rfloor\) 的 \(border\) 的数量。
我们先考虑暴力做法，我们直接对每个点跳 \(fail\) 树，统计有几个满足条件的 \(border\) 即可。但是显然这样做会 TLE。考虑换一种思路。
我们运用性质1容易得到对于一个 \(border\) ，比它短的加上它自身还有几个，等价于跳 \(fail\) 树去统计。那么我们得到这个东西（称为 \(num\) ）以及 \(fail\) 后，我们就可以再做一次自匹配，但是每匹配完一次就往回跳 \(fail\) 直到 \(border\) 长度不超过 \(\lfloor\frac{i}{2}\rfloor\) ，这个点的 \(num\) 就是答案。注意到多匹配一位肯定只会多算不会漏算，可得正确性没有问题。均摊复杂度是 \(O(n)\) 的。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
inline bool blank(const char &c){
return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
}
inline void gs(char *s){
char ch=gc();
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {*s++=ch;ch=gc();}
*s=0;
}
inline void gs(std::string &s){
char ch=gc();s+='#';
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {s+=ch;ch=gc();}
}
inline void ps(char *s){
while(*s!=0) pc(*s++);
}
inline void ps(const std::string &s){
for(auto it:s)
if(it!='#') pc(it);
}
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p*=0.1;ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=1e6+3;
const int mods=1e9+7;
int n;
char c[N];
int fail[N],num[N];
int ans;
inline int mul(int x,int y){
return 1ll*x*y%mods;
}
int main(){
filein(a);fileot(a);
int T;read(T);
while(T--){
gs(c+1);
int len=strlen(c+1);
int j=0;num[1]=1;
for(int i=2;i<=len;++i){
while(j and c[j+1]!=c[i]) j=fail[j];
if(c[j+1]==c[i]) ++j;
fail[i]=j;num[i]=num[j]+1;
//printf("[%d] ",num[i]);
//性质1
}//pc('\n');
j=0;ans=1;
for(int i=2;i<=len;++i){
while(j and c[j+1]!=c[i]) j=fail[j];
if(c[j+1]==c[i]) ++j;
while(2*j>i) j=fail[j];
ans=mul(ans,num[j]+1);
//printf("(%d) ",num[j]);
}//pc('\n');
printf("%d\n",ans);
}
return 0;
}
题目大意：多次询问，求两个前缀的最长公共前缀的长度。
容易发现，两者一同跳 \(fail\) 树直到出现公共部分，这不就是 \(fail\) 树上的 LCA 吗？然后根据 \(border\) 定义把 LCA 为两前缀之中的一个的情况特殊处理，再跳一步即可。
注意题面，不是求公共前缀有几个。（我也不知道我怎么看错的）
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
inline bool blank(const char &c){
return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
}
inline void gs(char *s){
char ch=gc();
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {*s++=ch;ch=gc();}
*s=0;
}
inline void gs(std::string &s){
char ch=gc();s+='#';
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {s+=ch;ch=gc();}
}
inline void ps(char *s){
while(*s!=0) pc(*s++);
}
inline void ps(const std::string &s){
for(auto it:s)
if(it!='#') pc(it);
}
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p*=0.1;ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=1e6+3;
char s[N];
int n,fail[N];
int fa[N][20+3],dep[N];
inline int LCA(int x,int y){
if(dep[x]<dep[y]) std::swap(x,y);
for(int i=20;i>=0;--i){
if(dep[fa[x][i] ]>=dep[y]){
x=fa[x][i];
}
if(x==y) return x;
}
for(int i=20;i>=0;--i){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
filein(a);fileot(a);
gs(s+1);
n=strlen(s+1);
int j=0;
dep[1]=1;
for(int i=2;i<=n;++i){
while(j and s[j+1]!=s[i]) j=fail[j];
if(s[j+1]==s[i]) ++j;
fa[i][0]=fail[i]=j;
dep[i]=dep[j]+1;
}
for(int i=0;i<20;++i){
for(j=1;j<=n;++j){
fa[j][i+1]=fa[fa[j][i] ][i];
}
}
int Q;read(Q);
while(Q--){
int a,b;
read(a,b);
int f=LCA(a,b);
if(f==a or f==b) f=fail[f];
printf("%d\n",f);
}
return 0;
}
题目大意：给一个字符串，问最短用一条多长的子串，能够将原串完全覆盖（不要求精准覆盖）。比如 \(aaa\) 可以用 \(a\) 完全覆盖。
发现这个子串必定是原串的 \(border\) ，在失配树上它们表现为一条链。然后我们证一个结论：只要在 \(u\) 的失配树子树中的点拿出来排序，相邻的最大间隔不超过 \(u\) ，那么 \(u\) 可以完全覆盖（前提还是 \(u\) 是原串的 \(border\)）。
这个不难证明，首先由于这些子树中的点都满足 \(u\) 是其 \(border\) ，那么可以把 \(u\) 从后往前接上，如果最大间隙不超过 \(u\) ，也就说明它的覆盖之间没有间隙，那么可以完全覆盖。
那么这个东西我们维护只删除的链表即可，我们在失配树上dfs，每次删掉父节点下除去原串 \(border\) 链所在子树的其他子树（父节点也要删），然后直接搞就没了。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
inline bool blank(const char &c){
return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
}
inline void gs(char *s){
char ch=gc();
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {*s++=ch;ch=gc();}
*s=0;
}
inline void gs(std::string &s){
char ch=gc();s+='#';
while(blank(ch) ) {ch=gc();}
while(!blank(ch) ) {s+=ch;ch=gc();}
}
inline void ps(char *s){
while(*s!=0) pc(*s++);
}
inline void ps(const std::string &s){
for(auto it:s)
if(it!='#') pc(it);
}
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);p*=0.1;ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
};
using IO::read;
using IO::gs;
using IO::ps;
const int N=5e5+3;
const int inf=1e9;
char c[N];
int fail[N],n;
int sta[N],top;
std::vector<int>G[N];
bool mark[N];
int mx=1;
struct list{
int l,r;
}p[N];
inline void del(int x){
mx=std::max(mx,p[x].r-p[x].l);
p[p[x].r].l=p[x].l;
p[p[x].l].r=p[x].r;
}
void dfs_del(int u){
del(u);
for(auto v:G[u]){
dfs_del(v);
}
}
int ans=0;
void dfs(int u){
if(mx<=u){
printf("%d\n",u);
exit(0);
}
del(u);
for(auto v:G[u]){
if(!mark[v])
dfs_del(v);
}
for(auto v:G[u]){
if(mark[v]){
dfs(v);
return;
}
}
}
int main(){
filein(a);fileot(a);
gs(c+1);
n=strlen(c+1);
G[0].push_back(1);
for(int i=2,j=0;i<=n;++i){
while(j and c[j+1]!=c[i]) j=fail[j];
if(c[j+1]==c[i]) ++j;
fail[i]=j;
G[j].push_back(i);
}
for(int i=n;i;i=fail[i]) mark[i]=1;
for(int i=0;i<=n;++i){
p[i].l=i-1;
p[i].r=i+1;
}
p[n].r=0;p[0].l=n;
dfs(0);
return 0;
}
性质2：
WPL（Weak Periodicity Lemma）：对于周期 \(p,q\) ，如果 \(p+q\le n\) ，那么 \(gcd(p,q)\) 也是周期。
证明：
我们假设 \(p<q\)，那么对于每个 \(i\) ，当 \(n-q+p\ge i>p\) 时，有 \(s[i]=s[i-p]=s[i-p+q]\) ；当 \(i<=p\) ，有 \(s[i]=s[i+q]=s[i+q-p]\)，那么对于每个 \(i\) ，有 \(s[i]=s[i+p-q]\)，那么可以得出结论 \(p-q\) 也是一个周期。
那么就知道了 \(p+(q-p)\le n\) ，一直搞下去等价于 \(gcd\) 辗转相减。那么其实对于所有能够辗转相减得到的都是周期，不一定非得 \(gcd(p,q)\)。
Q.E.D.
性质3：
对于两个字符串 \(s,t\) ，\(s\) 为 \(t\) 的前缀，\(t\) 有周期 \(a\) ，\(s\) 有周期 \(b\), 满足 \(a\le|s|\) 且 \(b|a\) ，那么有 \(b\) 为 \(t\) 的周期。
证明：
由于 \(b|a\) 且 \(a\le|s|\) ，所以可知 \(a\) 也为 \(s\) 的周期。又由于 \(s\) 为 \(t\) 的前缀，所以 \(s\) 完全覆盖 \(t\) 的前缀 \(a\)，那么 \(t\) 可以看做是有多个 \(s\) 的前缀 \(a\) 拼接而成。而显然对于 \(s\) 的前缀 \(a\)，其有周期 \(b\) ，而 \(t\) 又有周期 \(a\) ，那么 \(b\) 也为 \(t\) 的周期。
性质4：
对于两个字符串 \(s,t\) ，有 \(2|s|\ge |t|\)，则 \(s\) 在 \(t\) 上的匹配位置是一个等差数列。
证明：
不妨先将 \(t\) 未与 \(s\) 匹配的部分先剔除，然后设第一次匹配与第二次匹配位置相差 \(p\)，之后某次匹配与第一次匹配相差 \(q\) 。
我们可以得到 \(gcd(p,q)\) 位置也是一个匹配位置。由于 \(p\) 为第一次匹配位置，也即最小的匹配位置，显然有 \(gcd(p,q)=p\) ，那么可知 \(p|q\) 。显然那么 \(t\) 有周期 \(p\) ，每次匹配位置都相差 \(p\) ，因此在匹配位置上是公差为 \(p\) 的等差数列。
Q.E.D.
性质5：
对于一个字符串 \(s\)，其 \(\ge \frac{n}{2}\) 的 \(border\) 构成一个等差数列。
证明：
设最长 \(border\) 为 \(n-p\) ，某个 \(border\) 为 \(n-q\) ，且 \(p,q\le \frac{n}{2}\)。
那么可以知道，\(n-gcd(p,q)\) 也是 \(border\) ，然后由 \(n-p\) 为最长 \(border\) ，可知 \(gcd(p,q)\ge p\) ，即 \(p|q\)。那么其为公差为 \(p\) 的等差数列。
Q.E.D.
性质6：
一个字符串 \(s\) 的 \(border\) 按照长度排序后可划分为 \(O(\log n)\) 个等差数列。
证明：
先对于串对半分成两部分。然后可以发现后半段中的 \(border\) 形成等差数列，而前半段和后半段中的第一个 \(border\) 形成一个小的子问题。只需考虑后半段的第一个 \(border\) 的位置即可。
我们设后半段公差为 \(p\) 。\(p\le \frac{n}{4}\) 时，由最大 \(border\ n-p\) 连续减去 \(p\)，可得后半段的第一个 \(border\) \(\le \frac{3}{4}n\) ; \(p>\frac{n}{4}\) 时，\(n-p\) 就已经满足 \(\le \frac{3}{4}n\)，更不用说后半段的第一个 \(border\)。
由性质1，剩下的 \(border\) 都是这个后半段最小的 \(border\) 的 \(border\)，可知我们每次操作最少可以缩小到原范围的 \(\frac{3}{4}\) ，最多 \(\frac{1}{2}\) 。发现证不了它是 \(O(\log n)\) 的。
好吧，似乎换一种思路会更好。
我们将原串的 \(border\) 长度倍增地分为形如 \([2^{i-1},2^i)\) 的 \(O(\log n)\) 部分。
我们考虑区间 \([2^{i-1},2^i)\) ，其最大的 \(border\) 为 \(2^i-p\)，由性质1可知其他区间内的 \(border\) 都是这个最大 \(border\) 的 \(border\) 。然后由于性质3可以得知这个区间内的所有 \(border\) 构成公差为 \(p\) 的等差数列。
那么总共分了 \(O(\log n)\) 个区间，可以得到 \(O(\log n)\) 个等差数列。即使算上相邻两个区间的最大和最小 \(border\) 可能构成独一的等差数列的情况，也不过是多一份 \(2\) 的常数，总体依旧是 \(O(\log n)\)。其他情况只会少不会多。（但是实际上边界的 \(border\) 只会融入到两边的等差数列里面去）
Q.E.D.
性质7：
字符串 \(s\) 的公差 \(\ge d\) 的 \(border\) 等差数列的总大小为 \(O(\frac{n}{d})\) 的。
证明：
我们顺着性质6的证明来。对于一个区间 \([2^{i-1},2^i)\) ，公差 \(p\) 满足 \(p\le 2^i-2^{i-1}\) 。对于一个组内其大小为 \(\frac{2^i-2^{i-1}}{p}\)，那么公差 \(\ge d\) 的 \(border\) 等差数列的总大小就是:
\]
我们证明其上界，\(p_i\) 我们只少取不多取，取到 \(d\)；\(\sum 2^i-2^{i-1}\) 只多取不少取，取到 \(n\) 。那么总大小上界 \(\frac{n}{d}\) ，即总大小 \(O(\frac{n}{d})\)。
Q.E.D.
最新文章
- [原创]Centos7 从零编译Nginx+PHP+MySql
- python网络编程【一】
- 【转载】cmake编写
- session management
- [Java工具]Java常用在线工具集合.
- ArcGIS Javascript 异常之No 'Access-Control-Allow-Origin' header
- gulp小记(无刷新重载样式)
- 应用服务器上部署自己的 blog 和 wiki 组件。
- JDBC 连接池
- Spring messageSource
- injector
- Activity与Service之间交互并播放歌曲的实现代码
- TableView cell自适应高度-----xib
- 译文：ovs+dpdk中的“vHost User NUMA感知”特性
- typeof 与instanceof
- redis慢查询日志的配置和查看
- [转][linux]简单的linux下的tcp/udp
- elasticsearch 不同集群数据同步
- JavaScriptSerializer中日期序列化解决方案
- 谷歌技术"三宝"之MapReduce（转）