Skip to content
Shaoheng Nie
Go back

反向KMP问题出题历程回忆与题解

2025年11月30日,第11届中国大学生程序设计竞赛重庆站落下帷幕,我参与的最后一次命题工作也结束了。那是 code agent 爆发的前夜,距今不到一年时间,但那仍然是一个几乎全程用手敲代码出题,用人脑思考每一个细节的时代,在 agent 几乎包办智力活动的今天,回忆起来似乎是很久以前的事情了。

cqu-library

赛题中的K题是一道kmp算法相关的题目,也是我本场比赛中最喜欢的题之一。

缘起

复旦大学的计算机同学一定听说过孙未未老师的数据结构课,其难度远高于其他老师的同名课程。最显著的一个区别是,孙老师的课程每周有一次闭卷机考,考试的形式采用ACM赛制的OJ刷题,只是不按照罚时排名,只按照过题情况计分。为了考核的效果,题目需要不断更新,每届助教需要每周出至少一道原创题目。

大概是23年秋,我担任助教的时候,负责相关的出题工作,那段时光里,我会尽量每周到课堂中了解课程进度,然后根据课上知识点构思对应的原创题目,偶尔会特地避开一些知识点常见的考法。

那时起,我便开始构思一个KMP有关的有意思的问题:既然KMP算法的核心是对一个字符串求失配数组 {fn}\{f_n\},那么给定一个失配数组,能否刻画出其原来的字符串?比如,构造一个字符串能够得到对应的失配数组,或者判断不存在这样的字符串。

这个问题显然是容易的,因为字符串的第 ii 位 si=sfi, ∀fi>0s_i=s_{f_i},\ \forall f_i > 0 是失配数组的直接性质,它直接给出了 fi≠0f_i\ne 0 的位置字符和前面已有字符的等价关系。那么只需要在 fi=0f_i=0 的时候,给 sis_i 启用一个新增字符即可构造出来。这是我出给当时数据结构课的题目。

但那个时候我没有很快想明白一个问题:给定一个失配数组,如何构造一个字符集大小尽可能小的字符串?

图论模型

上面的问题容易建模为一个图论模型。可以把第 ii 个字符看做图上的节点,模拟kmp的 {fi}\{f_i\} 的求解过程可以得到一系列的相等和不等关系:

f[1]=0;
for(int i = 2; s[i] != '\0'; i++){
    int j = f[i-1];
    while(j && s[j+1] != s[i]) j = f[j];
    if(s[j+1] == s[i]) j++;
    f[i] = j;
}

可以看到,当跳失配指针的时候,会触发一个不等关系,当跳完后,则可能触发一次相等关系。

相等关系可以直接缩点合并来考虑,这样只用考虑互斥的二元关系。如此一来,构造字符串变成了经典的图染色问题:给定一张无向图,求合法染色方案,使得相邻节点颜色不同。

之前我想到这里便停止了,因为图染色问题,如果希望求解任意图的最小着色数量,显然是一个NPC问题。要想继续深入探索这个问题能否解,需要深挖该场景下图的性质。

弱化版

2025年7月,得知复旦大学需要进行两场CCPC命题(网络赛*1,重庆站*1),命题工作变得紧凑起来,我也把之前没有落实的 idea 给捡了起来。

在组题初期,这道“反向KMP”题目长这样:给定一个合法的失配数组,在字符集大小为3(即仅考虑由字符a,b,c组成的字符串)的字符串中,有多少个字符串具有给定的失配数组。

这个弱化版问题建立在上面图论模型的做法之上,其核心在于一个小的性质挖掘加上二着色问题可解。

直接套用图论建模,则是一个三着色计数问题,这在一般图上已经是NPC了。因此需要分析一些性质。

可以发现,字符串的第一个字符 s1s_1 可以看做一个锚点。剩下的每个字符,要么与它相同,要么与它连边(即一定存在确切的不等关系)。这是因为失配数组在求解的时候,任何一个 xx 若满足 fx=0f_x=0 ,那么它一定和 s1s_1 比较过,并且有 sx≠s1s_x\ne s_1。所以图论模型在这种情况下,假如把相等关系的字符进行缩点,那么缩完后的图中,假设存在 mm 个点,可以得出存在一个点 11 与剩下 m−1m-1 个点均相连。

那么只要 s1s_1 的字符(3种选择)确定了,其他所有的点仅有两种剩下的颜色可选,于是变成了2着色问题。答案就是 3×3\times “删除1号点后剩余子图的2着色方案数” 。而2着色问题只需要验证图中每个连通块是否是二分图就行了:若存在非二分图连通块,则答案为0,否则答案为 2p2^{p} ,其中 pp 为连通块个数。

这个弱化版一度将要成为最后的版本,直到验题的时候mc大神给出了一个贪心做法……

贪心做法

有些天赋型选手天生能够敏锐地捕捉到特殊性质,当时mc的贪心做法让人眼前一亮。

为了凸显核心思路,下面这段代码移除了对失配数组合法性判断的部分逻辑。

int n,m,f[MAXN];
char s[MAXN];
void Main(){
    cin>>n>>m; // 只处理字符集size m=3 的情况
    For(i,1,n) cin>>f[i];
    LL ans=1;f[0]=-1;
    For(i,1,n){
        s[i]=0;
        if (f[i]!=0){ 
            s[i]=s[f[i]]; // 存在相等关系,直接标记等价类
        }else{  
            int j=f[i-1];
            bool vs[3]={0};
            for (;j!=-1;j=f[j]) vs[s[j+1]-'a']=1; // 标记跳失配数组时产生的互斥等价类
            int num=0; // num 用来统计不互斥的等价类数量
            For(j,0,2){
                if (s[i]==0&&vs[j]==0) s[i]='a'+j;
                num+=(!vs[j]);
            }
            ans=1LL*ans*num%MOD;
        }
    }
    cout<<ans<<"\n";
}

该算法直接模拟了失配数组求解的过程,并按照 fif_i 与 0 的关系分两类讨论。如果 fi≠0f_i\ne 0 ,直接标记 sis_i 属于的等价类。否则,sis_i 一定属于一个新增的等价类,只需要模拟 sis_i 失配求解过程中在跳失配指针时产生的所有互斥关系,统计互斥的等价类个数,就得到了 sis_i 可以取的字符种数,然后在这些字符中随便给它一个字符标记为它的等价类标志即可。

把每个新增等价类的可取字符数乘起来就是答案。

只能说,数感不是人人都有的,这个做法在mc看起来及其自然、符合直觉、一眼合理,但是在我眼里就显得不那么能理解了。比如,为什么随便赋值一个失配链上不互斥字符就可以保证这套算法正确性?

但是在丰富的对拍数据下确实没有问题,让我不得不尝试证明这个做法的正确性。

推广到字符集大小为 mm

最终,在和 mc 以及 OIer_kzc 的讨论下我们完成了证明和问题的推广,并决定在比赛中将这道题的 mm 加强到 O(n)O(n) 同级。

要证明mc思路的正确性,还是需要回到图论模型上,去分析每一个互斥关系的作用。

互斥链

在模拟失配数组求解过程中,可以认为,每个 fif_i 在求解时,都需要跳一条从 i−1i-1 状态开始的失配链。这个链条可以记作:i−1, fi−1, ffi−1⋯0i-1,\ f_{i-1},\ f_{f_{i-1}}\cdots 0。 在跳到状态 xx 的时候,我们匹配的字符是 sx+1s_{x+1} 。所以不妨把这条链看成带权链,链上每个状态权值即为 val(x)=sx+1val(x) = s_{x+1}。

我们从 i−1i-1 出发开始跳,直到跳到链上的状态 yy 满足 val(y)=val(i−1)val(y) = val(i-1) 为止(或者跳完链后发现并没有满足条件的状态),而在这个过程中跳过的其他状态都会标记为互斥。

后面所有的分析都基于此带权链。

分支1:fi≠0f_i\ne 0

算法对于 fi≠0f_i\ne 0 的场景,直接把 ii 节点和 fif_i 节点合并了,不做其它处理。这意味着,我们需要证明,在此分支上失配链上的所有互斥关系都已经在之前考虑过了,在图染色模型中属于多余的边。

观察失配链 i−1, fi−1, ffi−1⋯fi−1i-1,\ f_{i-1},\ f_{f_{i-1}}\cdots f_i - 1 我们知道该分支下有 val(i−1)=val(fi−1)val(i-1) = val(f_i - 1) ,且中间的各个状态的权值与两端不同。

注意到失配链在迭代过程中是单向增加的,意味着在我们处理状态 ii 之前,也处理过状态 fi−1+1f_{i-1}+1,所以曾经跳过 fi−1, ffi−1⋯fi−1f_{i-1},\ f_{f_{i-1}}\cdots f_i - 1 这条链,因此可以假设已经处理过了 val(fi−1)val(f_{i-1}) 与 val(fi−1)val(f_i-1) 的不等关系,而因为 val(i−1)=val(fi−1)val(i-1) = val(f_i - 1) 所以无需再处理 val(i−1)val(i-1) 与 val(fi−1)val(f_{i-1}) 的不等关系。

因此这个部分容易用数学归纳法证明。

另外,可能看起来有个小漏洞,就是链条状态 fi−1f_{i-1} 在跳链的时候不一定会经过 fi−1f_i-1 ,有可能到和它同权值状态就停止了。例如,链条上的权值为 a,b,c,b,a……,那么从第2个状态跳的时候到第4个状态就停止了,似乎没有考虑到链上第2,5状态之间的不等关系。但是,在更早的时候处理从第4个状态的b开始跳的时候,则处理了链上第4,5状态之间的不等关系,而2,4状态等价,因此没有漏洞。

所以其实本质在于,在我们跳失配链过程中,只要链上有本次状态的等价状态,跳链过程中遇到的不等状态,肯定都在更早的时候考虑过与本次状态的等价状态的不等关系。

分支2:fi=0f_i= 0

在这种情况下,说明跳失配链的时候,链上所有权值都与本状态不等。此时我们建立了一个着色图模型上的新结点,它与失配链上所有出现过的权值结点连边。

那么,这个新结点的染色方案就取决于 mm 减去链上已经存在的权值种类数。

最后,只需要把每个结点的染色方案数乘起来就是最后的方案种数了。因为失配链的拓展过程形成的是一棵单向树,按照此树的拓展顺序进行图着色,处于树上不同分叉的结点染色互不干扰,非常优雅的性质。

最终算法

我们只需要在失配树的拓展过程中,维护当前结点 ii 到根结点 00 中,已经存在的等价类数量 cic_i。在新增状态 fi=0f_i= 0 的时候,我们有 ci−1=cfi−1+1c_{i-1} = c_{f_{i-1}} + 1,并且给最终答案累乘 m−ci−1+1m-c_{i-1}+1 即可。 否则,直接维护 ci−1=cfi−1c_{i-1} = c_{f_{i-1}} 即可。

另外,无解的情况需要稍许特判,因为输入不保证给定的失配数组合法。这一点也是希望在区域赛上多加一点细节考查。

#include<bits/stdc++.h>
#define LL long long
#define MAXN 1000010
#define INF 1000000010
#define INFLL (1LL*INF*INF)
#define MOD 998244353
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Rof(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
int n,m,nxt[MAXN];
int num[MAXN];
int s[MAXN];
void Main(){
    cin>>n>>m;
    For(i,1,n) cin>>nxt[i];
    LL ans=1;nxt[0]=-1;num[0]=0;
    For(i,1,n){
        s[i]=0;
        if (nxt[i]!=0){
            s[i]=s[nxt[i]];
            int j=nxt[i-1];
            for (;j!=-1&&s[j+1]!=s[i];j=nxt[j]);
            if (j+1!=nxt[i]){
                cout<<0<<"\n";
                return ;
            }
        }else{
            ans=1LL*ans*(m-num[i-1])%MOD;
            s[i]=num[i-1]; 
            num[i-1]+=1;
        }
        num[i]=num[nxt[i]];
    }
    cout<<ans<<"\n";
}   
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // INIT();
    int T=1;cin>>T;
    For(i,1,T) Main();
    exit(0); 
}

后记

2026年的国庆,在假期的间隙中,我回忆起了这道题目,在重庆站赛后我本该当即写下这份题解博客,但当时苦于毕业和秋招的压力,搁置了。现在回忆起来,这是我在 code agent 爆发前最后一次出题的题目了。

在今天这个无所不能的时代,无论是工作还是生活中,太多事情都可以让agent代办了,我们似乎不再需要思考问题的细节,因为这些都可以让agent在几轮迭代中完善。从效率的角度上讲,我大可以用agent一键生成所有的题解博客,尤其是近期“Astra大人”的神威掀起了爆标狂潮。但我始终觉得,我的脑子里好像少了些什么。

本科期间我热衷于写博客,我热衷于分享知识,我喜欢沉浸思考一个问题的过程,我会在得到有趣结论后获得巨大的成就感。但是在今天,代码可以AI写,结论可以AI出,出于效率考虑,我只需要做一个阅读者,验证理解AI的答案。但是缺少了思考的过程,一切似乎都变得无趣,甚至长此以往让我失去了思考的耐心。

在假期的间隙里,我用一小时多的时间在脑海里又重新推导了这道题目演变的每个细节,然后,用了约一个下午的时间亲手敲了这篇博客。我已经很久没有如此纯粹的创作体验了。我时常在想,如果AI替代了大部分的智力活动,彻底冲击了现有的评价体系,我们曾经做的一切还有意义吗?

如果AI直接告诉我这道题的答案,我或许会惊叹于这个题目的精妙,但我再也不会体验到出这道题目的过程中,探索的过程带给我的快乐了。

彩蛋


Share this post on:

Next Post
如何配置 AstroPaper 主题