djwj233 的博客

djwj233 的博客

基础字符串 学习笔记

posted on 2021-10-03 20:40:21 | under 笔记 |

本文主要整理了:

  • 字符串的基础概念与定义
  • 基础 Border 理论
  • KMP 算法

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

概念与定义

(只会记录一些我不太会的定义)

基础概念

  • 字符集 $\Sigma$ 生成的所有字符串的集合为 $\Sigma^*$。可以看到,若 $\Sigma\ne \varnothing$,则 $\Sigma^*$ 为无穷集。
  • 定义空串为长度为 $0$ 的串,记为 $\epsilon$。$\epsilon$ 是任意群 $(\Sigma^*,+)$ 中唯一的零元。($+$ 表示拼接操作)
  • 拼接操作可被记为 $C=A+B$,也可写作 $C=AB$。
  • 记一个字符串 $S$ 的反串为 $S^R$,那么 $S$ 为回文串当且仅当 $S=S^R$。注意:$\epsilon$ 也是回文串。

周期结构

  • 定义 $x$ 是 $S$ 的周期(Period),当且仅当 $x\le |S|$ 且 $\forall i\in[1,|S|-x],\ S_i=S_{i+x}$。

    若 $x$ 整除 $|S|$,则称 $x$ 是 $S$ 的一个整周期

  • 定义 $T$ 是 $S$ 的 Border(缩写为 Bd),当且仅当 $T$ 同时是 $S$ 的真前缀真后缀

    同时也称 $|T|$ 是 $S$ 的 Border。

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

Border 理论的基本性质

  • 性质:$p$ 是 $S$ 的周期,当且仅当 $|S|-p$ 是 $S$ 的 Border.

十分显然,证明略。

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

  • 弱周期引理(Weak Periodicity Lemma):若 $p,q$ 是 $S$ 的周期,且 $p+q\le |S|$,则 $\gcd(p,q)$ 也是 $S$ 的一个周期。

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

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

$\forall x\in[p+1,p+q]$,有 $S_x=S_{x-p}=S_{x-q}$。因此有 $\forall x\in [1,q],\ S_x=S_{x+p-q}$。

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

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

  • 周期引理(Periodicity Lemma):若 $p,q$ 是 $S$ 的周期,且 $p+q-\gcd(p,q)\le |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$,因此周期引理的上界是紧的。

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

  • 长字符串的匹配定理:若 $2|S|\geq|T|$,则 $S$ 在 $T$ 中的匹配位置必为等差序列。

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

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

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

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

  • 短周期结构:字符串 $S$ 有不超过 $\dfrac{|S|}{2}$ 的周期 $y$,当且仅当 $y$ 是其最短周期 $x$ 的倍数。

证明:充分性是显然的,下证必要性。

若 $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$ 成立。

  • 长 Border 结构:字符串 $S$ 的所有不小于 $\dfrac{S}{2}$ 的 Border 构成等差数列,且如果排序后延申这个数列,下一项就是 $|S|$。

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

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

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

  • 字符串的周期/Border 结构:字符串 $S$ 的所有周期或 Border 形成了 $\mathcal O(\log n)$ 个值域不交的等差数列

证明:有一个结论是,若 $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 算法,给出如下结论:

  • 性质:设 $S[1\cdots i]$ 的所有 Border 长度所形成的集合为 $\mathrm{Bd}_i$,则有:$$ \mathrm{Bd}_i=\begin{cases} \{0\} & \pi(i)=0\\ \mathrm{Bd}_{\pi(i)}\cup{\pi(i)} & \pi(i)>0 \end{cases} $$

证明:易证 $\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;
}