基础字符串 学习笔记

· · 个人记录

本文主要整理了：

有些贺自 ix35 的博客。限于篇幅和本文偏应用的目的，会略去大多数性质的证明。

概念与定义

（只会记录一些我不太会的定义）

基础概念

周期结构

容易看出 |S| 是任意字符串 S 的平凡周期，0 或 \epsilon 是其平凡 Border。

Border 理论的基本性质

十分显然，证明略。

不过这确实是一条非常有用的结论，借助它可以用 KMP 在 \mathcal O(n) 内求出字符串的所有周期。

证明：观察有 \gcd(p,q) 的形式，猜想可以用辗转相除的思路证明。

当 p=q 时显然成立，因此不妨设 p>q，我们证明 p-q 也是 S 的一个周期。

而 $\forall x>q,\ S_x=S_{x-q}=S_{x+p-q}$，可知 $p-q$ 是 $S$ 的一个周期，再借用辗转相除法得 $\gcd(p,q)$ 是 $|S|$ 的周期。

实际上这个引理可以进一步加强：

取 S=\texttt{abacaba}，p=6,q=4。则 \gcd(6,4)=2 不是 S 的一个循环节。

同时我们注意到 p+q-\gcd(p,q)=8=|S|+1，因此周期引理的上界是紧的。

具体证明用到生成函数，就不管了。

证明：易见 S 在 T 中的多个匹配必然有重叠的部分。

考虑去掉 T 中没有被覆盖的字符，然后考虑反证。

设有三个最近的匹配相距分别 p,q(p\ne q)，我们发现这三个匹配覆盖的字符串一定有周期 p,q。

于是便可以利用弱周期引理证明 \gcd(p,q) 也是它们的周期，于是便可以构造出它们中间的一组匹配，推翻假设。

证明：充分性是显然的，下证必要性。

若 x>\dfrac{|S|}{2} 或 y=x，则结论已成立。下面假设 x\le \dfrac{|S|}{2},y>x，对任意 S 的周期 y\le \dfrac{|S|}{2}，即有 x+y\le|S|。

因此 y-x 也是 |S| 的周期。若 x\nmid y，设 y\equiv r\pmod{x}，则可以找出一个周期 r<x，构成矛盾。

故总有 x\mid y 成立。

证明：由短周期结构的结论，字符串 S 的所有不超过 \dfrac{|S|}{2} 的周期成等差数列。

由上面的性质可知长 Border 也成一个这样的等差数列。

简单的说，以 \dfrac{|S|}{2} 为界，短周期和长 Border 分别成等差数列。

证明：有一个结论是，若 p 和 q\ (p<q) 都是 S 的 Border，则 p 也是 S[1\cdots q] 的 Border。

  • 设 S 的最长 Border 长度为 b_0，有 b_0<|S|，且：

    • 长度在 [\dfrac{b_0}{2},b_0] 之间的 Border 都是 S[1\cdots b_0] 的 Border，成一个等差数列；

  • 设最长的小于 \dfrac{b_0}{2} 的 Border 长度为 b_1，有：

    • 长度在 [\dfrac{b_1}{2},b_1] 之间的 Border 都是 S[1\cdots b_1] 的 Border，成一个等差数列；

此时我们已证明长度在 [\dfrac{|S|}{2^2},|S|] 之间的 Border 成至多 2 个等差数列，同上简单归纳可知结论成立。

这里刻画了大于 \dfrac{|S|}{2} 的周期 / 小于 \dfrac{|S|}{2} 的 Border 的性质。

这里是一个错解，没有考虑到短周期结构只对不大于 \dfrac{|S|}{2} 的周期适用。

那么还怎么做呢？可以考虑同余最短路，跑出来再进行转移，具体看题解。

可以发现，求一个数列的线性组合一般使用同余最短路。

（好像写歪了）总复杂度 \mathcal O(Tn\log n)。

一直调不出！！！！！！

前缀函数与 KMP 算法

Knuth-Morris-Pratt 算法是一种能在 \mathcal O(n) 内求出字符串 S 的前缀函数 / 将另一个字符串 T 和 S 进行匹配的算法。

定义：S 的前缀函数（Prefix function）\pi(i) 表示 S[1\cdots i] 的最长 Border 长度。

为引出 KMP 算法，给出如下结论：

证明：易证 \complement_{\mathrm{Bd}_{i}}\{0\}\subseteq\mathrm{Bd}_{\pi(i)}，再由反证法可证明 \mathrm{Bd}_{\pi(i)}\subseteq\mathrm{Bd}_i。详细证明略去。

现在来研究如何求出 \pi(i)。

由于复杂度要求是 \mathcal O(n) 的，因此我们考虑从 \pi(i-1) 导出 \pi(i)。

我们发现，由前缀函数的定义，\pi(i)\le\pi(i-1)+1，否则 \pi(i)-1 一定是 \pi(i-1) 的一个更优的解。

同理也可以得到 \pi(i)-1\in \mathrm{Bd}_{i-1}，那么我们从大到小枚举 \mathrm{Bd_{i-1}} 中的数 j，直到 S_{j+1}=S_i（可以扩展一位）或 j=0（匹配失败）。

一般在代码中把 \pi(i) 写作 \texttt{next} 数组或 \texttt{fail} 数组，代码如下：（注意要从 i=2 开始枚举）

int j=0; Next[1]=0;
fo(i,2,n) {
    while( j>0 && s[j+1]!=s[i] )
        j=Next[j];
    if(s[j+1]==s[i]) j++;
    Next[i]=j;
}

然后处理如何在 S 中匹配 T，我们发现这个过程和上面是类似的。

下面我们来分析它的复杂度。

可以看出，第 3 行的 while 循环每执行一次至少会使 j 的值减小 1，而 j 总共被增加了不超过 n 次。

因此第 3 行的 while 循环至多会执行不超过 \mathcal O(n) 次，总复杂度是 \mathcal O(n) 的。

直接把上面的东西写出来：

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline

const int N=1000010;

int n,m,Next[N];
char s[N],t[N];

int main()
{
    scanf("%s",t+1), m=strlen(t+1);
    scanf("%s",s+1), n=strlen(s+1);

    int j=0; Next[1]=0;
    fo(i,2,n) {
        while( j>0 && s[j+1]!=s[i] )
            j=Next[j];
        if(s[j+1]==s[i]) j++;
        Next[i]=j;
    }
    j=0;
    fo(i,1,m) {
        while( j>0 && s[j+1]!=t[i])
            j=Next[j];
        if(s[j+1]==t[i]) j++;
        if(j==n) printf("%d\n",i-j+1);
    }
    fo(i,1,n) printf("%d ",Next[i]);
    puts("");

    return 0;
}

实际上，由于 NOI 大纲中不高于提高级的字符串算法只有 KMP，因此碰到联赛范围以内的字符串题不会做时，一般都是先跑一遍 KMP 求出 \pi(i) 然后找性质。

例题

感觉有点偏（

维护一个答案字符串，每次都对需要加入的字符串算出 \pi(i)，然后在答案字符串上进行正序的匹配。

具体做法可参考代码。Code

看到 m\le20 而 n\le 10^9 十分诡异，考虑矩乘。

我们考虑一个 DP，记 dp_{i,j} 为当前到第 i 位，还没有不合法子串但当前有 j 位匹配上了。

然后跑一遍 KMP 处理矩阵的系数，就可以愉快地矩阵快速幂了。

Code

失配树

给出失配树（Border Tree）的定义：

对于每个 i，我们连边 i\to\pi(i)，便可得到一棵以 0 为根的树，不难发现这棵树满足小根堆性质。

那么，一个前缀 S[1\cdots i] 的所有 Border 就是 i 在树上的所有祖先。

失配树有什么用呢？它可以将一个字符串问题转化为我们熟悉的树论问题。

这是显然的。这样我们可以给出这棵树的一个拓扑序为 \{n,n-1,\cdots,1\}。

这样我们在失配树上 DP 时就不用写 DFS 了

例题

给出一个字符串 S，求 S 的两个长度分别为 n 和 m 的前缀的最长公共 Border 长度。

不难发现，只要建出失配树，\operatorname{LCA}(n,m) 就是答案。

但是，真的是 \operatorname{LCA}(n,m) 吗？我们发现，若 n,m 中有一个是另一个的祖先，则答案为它的父亲。

特判即可。Code

这题大致是让我们对每个 i 求出 \mathrm{Bd}_i 中 \le \dfrac{i}{2} 的元素个数。

暴力肯定要超时，貌似可以倍增，但算算复杂度发现它没有前途。

我们考虑从树上入手。

一种做法是 DFS 一遍树然后移指针，但是移指针很费时间，能卡到 \mathcal \Theta(n^2)，参见 ZCETHAN 被 hack 的记录。

我的做法是先正着算出每个点的深度，再从大到小枚举 i，然后像并查集那样合并结点。由于每个点只会被合并一次，所以复杂度是 \mathcal O(n) 的。

Code

题解区有一种做法是算出深度后模拟一遍 KMP 过程：

fo(i,1,n) {
    while( j>0 && s[j+1]!=s[i]))
        j=Next[j];
    if(s[j+1]==s[i]) j++;
    while(2*j>i) j=fail[j];
    res=res*(ll)(ans[j]+1)%P;
}

这个做法主要考虑到如果一个 Border 在某个位置不合法，那么由它扩展的都不会合法。

非常神仙的一道题。

我们考虑一个 DP，设 dp_i 表示要印出 S[1\cdots i] 至少需要多长的印章，不难发现 dp_1=1，且：

\forall i\in [1,|S|],\ dp_i\in \mathrm{Bd}_i\cup \{i\}

也就是说，dp_i 在失配树中 i 和 \mathrm{anc}(i) 中取值，若 \pi(i)=0，则 dp_i=i。

若 dp_i<i，则 dp_i\le \pi(i)，S[1\cdots dp_i] 能覆盖 S[1\cdots\pi(i)]。

因此有 dp_i\geq dp_{\pi(i)}，dp 数组在失配树的一条链上呈一个单调性。

然后就不会了，看了这篇题解，然后就发现自己是 sb。

因为如果 dp_i 取到 (dp_{\pi(i)},\pi(i)] 之间的数，那么因为它的某个 Border 一定是 dp_{\pi(i)}，且由 dp_{\pi(i)} 的性质，dp_{\pi(i)} 一定能生成这个字符串。

因此它能生成的所有串一定是 dp_{\pi(i)} 所生成的子集。换句话说，取答案为 (dp_{\pi(i)},\pi(i)] 之间的数一定不比 dp_{\pi(i)} 优。

考虑什么时候我们被迫取 dp_i=i，我们发现当且仅当 S[1\cdots \pi(i)] 无法覆盖 S[1\cdots i] 时才取 dp_i=i。

这可以用一个桶维护，代码见下。

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline

const int N=500010;

int n; char s[N];
int Next[N],dp[N],pre[N];

int main()
{
    scanf("%s",s+1), n=strlen(s+1);

    int j=0; Next[1]=0;
    fo(i,2,n) {
        while( j>0 && s[j+1]!=s[i] )
            j=Next[j];
        if(s[j+1]==s[i]) j++;
        Next[i]=j;
    }

    dp[1]=1, pre[1]=1;
    fo(i,2,n) {
        if( pre[dp[Next[i]]]+dp[Next[i]] >= i)
            dp[i]=dp[Next[i]];
        else dp[i]=i;
        pre[dp[i]]=i;
    }
    printf("%d\n",dp[n]);

    return 0;
}