前几天后台收到一条私信“学长第四范式的算法笔试题到底考什么我刷了几百道LeetCode结果看到题还是懵。”这条私信让我想起自己当年投算法工程师时在牛客网上做第四范式笔试题的那个晚上——题量不大题干短到不像大厂风格可恰恰是这种短题干里藏着KMP的next数组、循环节判定、整除性推导这些基本功。平时刷题的时候这些内容最容易被一带而过真到了考场就露馅。今天我就以这套2019年校园招聘算法笔试题里一道很有代表性的“字符串循环节”题为例把从读题、推公式、写代码到考后复盘的全过程拆开讲清楚。如果你正在准备算法岗笔试这篇内容能帮你省掉不少自己摸索的时间。1. 从第四范式的业务基因看笔试为什么这样出题1.1 一家做AI平台的公司为什么先考算法第四范式做的事情通俗讲就是把机器学习能力沉淀成企业级平台帮金融、零售、制造这些行业里的公司做风控、营销、决策优化。它招算法工程师时笔试不会出脑筋急转弯式的偏题而是非常朴素地考察三件事数据结构基本功、算法设计能力、边界处理习惯。很多人有个误判觉得AI公司的笔试应该考模型调参、考TensorFlow/PyTorch、考深度学习框架。实际上在线笔试环节就是考算法题模型和项目更多是在面试环节口头考察。你算法基础不过关简历筛选过了也走不到面试。字符串题在这类公司笔试里出现频率极高。原因也很直白不管是文本特征处理、日志异常检测还是推荐系统里的序列建模都绕不开字符串处理。KMP、Trie、字符串哈希这些内容不是“竞赛专属”是工程日常。1.2 笔试题型的常见框架与时间压力2019年这一届的笔试我根据身边同学和自己的考场经验还原一下整体配置总时长大概90分钟2道编程题加1道简答题。编程题难度大约在LeetCode中等偏上但不会直接给你“实现一个LRU缓存”这种大路货而是会换一层皮让你现场推公式。简答题会偏机器学习基础比如过拟合与正则化、偏差方差权衡、GBDT的近似分裂思想。这些内容之后可以单独写一篇今天先把编程题拆透。时间压力是真实存在的。90分钟看着不少但第一道题通常要20分钟第二道题如果思路卡住很容易耗掉40分钟以上最后简答题只能仓促写几句。所以做题顺序和时间分配我放到后面专门讲。1.3 这道字符串题的考场位置这套题里有一道题题干极短但区分度很高。它表面上是让算一个模式串的next数组实际在考你能不能把KMP从“字符串匹配模板”升级为“周期判定工具”。很多考生把KMP模板背得滚瓜烂熟一遇到这种变形就只能在原模板上改输入输出结果错得莫名其妙。题目本身不冷门核心就是KMP的next数组与最小循环节判定。下面我把考后回忆的题面还原出来并完整拆解。2. 还原考场原题字符串循环节题与考点拆解2.1 题面与输入输出格式根据考生回忆原题题面大意如下给定一个字符串s长度不超过10^6仅包含小写字母。 对每个前缀位置L1 L n判断s的前缀 s[0..L-1] 是否能由某个更短的字符串t重复至少2次得到。 如果能输出两个整数最小周期长度 d 和重复次数 k 如果不能输出 -1。输入样例1abab输出样例1-1 -1 -1 2 2解释一下这个样例前缀长度为1时是a长度为2时是ab长度为3时是aba都不能由更短串重复构成。长度为4时是abab由ab重复2次得到最小周期长度是2重复次数是2。输入样例2就是我们熟悉的abacaba输出样例2-1 -1 -1 -1 -1 -1 -1整串abacaba看起来好像有点规律但确实不能由某个更短的串重复至少2次构成。具体为什么下面用next数组算一遍就清楚了。2.2 这道题真正在考什么这个题面看起来简单背后有四个考点求每个前缀的最长相等前后缀长度这正是KMP预计算阶段做的事用nxt[L]推出候选周期 d L - nxt[L]判断是否满足 L % d 0 且 d L决定该前缀能否由更短串重复构成处理边界条件L1、整个串本身不是循环串时都要输出-1。暴力做法会超时得很惨。比如对每个前缀枚举所有可能因子d再逐个位置比较最坏情况是O(n^2)n到10^6时完全跑不动。所以这道题想考察的就是你能不能想到用KMP的next数组把判定压缩到O(n)。2.3 为什么“next数组”是解题钥匙KMP算法里有一步是预处理模式串的next数组匹配阶段靠它实现失配后不回退主串指针。而next数组本身蕴含的信息比“失配回退”更丰富——它记录的是每个前缀的“最长相等前后缀”长度这个信息天然可以用于周期判定。换句话说这道题表面考的是循环节实际考的是你对next数组本质的理解。如果你只是单纯背模板不知道next数组里存的是什么这道题基本做不出来。3. KMP的next数组两种定义与一次手算推演3.1 next数组的本质最长相等前后缀先说清楚什么是“最长相等前后缀”。对于一个字符串prefix它的前缀和后缀不能包含字符串自身。比如abacab最长相等前后缀是ab长度为2。next数组记录的就是这个信息但不同教科书定义不同这是很多考生搞混的根源。我统一采用下面的定义Anxt[i] 表示字符串前 i 个字符即 s[0..i-1] 的最长相等前后缀长度。 nxt[0] -1作为递推起点。失配回退时直接 j nxt[j] 就能跑代码不容易记混。至于另一种定义B后面我会专门讲区别。3.2 手算“abacaba”的完整过程设模式串 p abacaba我们用定义A手算nxt数组。初始时nxt[0] -1 i 0, j -1KMP预计算的递推过程如下第1步j -1进入基础分支。 i 1, j 0, nxt[1] 0 第2步i1, j0比较 p[1]b 与 p[0]a不等。 j nxt[0] -1 第3步j -1进入基础分支。 i 2, j 0, nxt[2] 0 第4步i2, j0比较 p[2]a 与 p[0]a相等。 i 3, j 1, nxt[3] 1 第5步i3, j1比较 p[3]c 与 p[1]b不等。 j nxt[1] 0 第6步i3, j0比较 p[3]c 与 p[0]a不等。 j nxt[0] -1 第7步j -1进入基础分支。 i 4, j 0, nxt[4] 0 第8步i4, j0比较 p[4]a 与 p[0]a相等。 i 5, j 1, nxt[5] 1 第9步i5, j1比较 p[5]b 与 p[1]b相等。 i 6, j 2, nxt[6] 2 第10步i6, j2比较 p[6]a 与 p[2]a相等。 i 7, j 3i到达串尾结束。最终得到nxt [-1, 0, 0, 1, 0, 1, 2]注意nxt[7]也在构建过程中算出来了等于3它表示整个串abacaba的最长相等前后缀是aba长度为3。3.3 两种next定义的坑与换算很多教材用的是另一种定义next[i] 表示 s[0..i] 的最长相等前后缀长度。这种情况下abacaba的next数组是next [0, 0, 1, 0, 1, 2, 3]两种定义有个简单的换算关系定义B的next[i]等于定义A的nxt[i1]。| 下标i | 字符 | 定义Anxt[i] | 定义Bnext[i] | | 0 | a | -1 | 0 | | 1 | b | 0 | 0 | | 2 | a | 0 | 1 | | 3 | c | 1 | 0 | | 4 | a | 0 | 1 | | 5 | b | 1 | 2 | | 6 | a | 2 | 3 | | 7 | 串尾 | 3 | 无 |做题
KMP算法笔试题解析：用next数组判断字符串循环节
前几天后台收到一条私信“学长第四范式的算法笔试题到底考什么我刷了几百道LeetCode结果看到题还是懵。”这条私信让我想起自己当年投算法工程师时在牛客网上做第四范式笔试题的那个晚上——题量不大题干短到不像大厂风格可恰恰是这种短题干里藏着KMP的next数组、循环节判定、整除性推导这些基本功。平时刷题的时候这些内容最容易被一带而过真到了考场就露馅。今天我就以这套2019年校园招聘算法笔试题里一道很有代表性的“字符串循环节”题为例把从读题、推公式、写代码到考后复盘的全过程拆开讲清楚。如果你正在准备算法岗笔试这篇内容能帮你省掉不少自己摸索的时间。1. 从第四范式的业务基因看笔试为什么这样出题1.1 一家做AI平台的公司为什么先考算法第四范式做的事情通俗讲就是把机器学习能力沉淀成企业级平台帮金融、零售、制造这些行业里的公司做风控、营销、决策优化。它招算法工程师时笔试不会出脑筋急转弯式的偏题而是非常朴素地考察三件事数据结构基本功、算法设计能力、边界处理习惯。很多人有个误判觉得AI公司的笔试应该考模型调参、考TensorFlow/PyTorch、考深度学习框架。实际上在线笔试环节就是考算法题模型和项目更多是在面试环节口头考察。你算法基础不过关简历筛选过了也走不到面试。字符串题在这类公司笔试里出现频率极高。原因也很直白不管是文本特征处理、日志异常检测还是推荐系统里的序列建模都绕不开字符串处理。KMP、Trie、字符串哈希这些内容不是“竞赛专属”是工程日常。1.2 笔试题型的常见框架与时间压力2019年这一届的笔试我根据身边同学和自己的考场经验还原一下整体配置总时长大概90分钟2道编程题加1道简答题。编程题难度大约在LeetCode中等偏上但不会直接给你“实现一个LRU缓存”这种大路货而是会换一层皮让你现场推公式。简答题会偏机器学习基础比如过拟合与正则化、偏差方差权衡、GBDT的近似分裂思想。这些内容之后可以单独写一篇今天先把编程题拆透。时间压力是真实存在的。90分钟看着不少但第一道题通常要20分钟第二道题如果思路卡住很容易耗掉40分钟以上最后简答题只能仓促写几句。所以做题顺序和时间分配我放到后面专门讲。1.3 这道字符串题的考场位置这套题里有一道题题干极短但区分度很高。它表面上是让算一个模式串的next数组实际在考你能不能把KMP从“字符串匹配模板”升级为“周期判定工具”。很多考生把KMP模板背得滚瓜烂熟一遇到这种变形就只能在原模板上改输入输出结果错得莫名其妙。题目本身不冷门核心就是KMP的next数组与最小循环节判定。下面我把考后回忆的题面还原出来并完整拆解。2. 还原考场原题字符串循环节题与考点拆解2.1 题面与输入输出格式根据考生回忆原题题面大意如下给定一个字符串s长度不超过10^6仅包含小写字母。 对每个前缀位置L1 L n判断s的前缀 s[0..L-1] 是否能由某个更短的字符串t重复至少2次得到。 如果能输出两个整数最小周期长度 d 和重复次数 k 如果不能输出 -1。输入样例1abab输出样例1-1 -1 -1 2 2解释一下这个样例前缀长度为1时是a长度为2时是ab长度为3时是aba都不能由更短串重复构成。长度为4时是abab由ab重复2次得到最小周期长度是2重复次数是2。输入样例2就是我们熟悉的abacaba输出样例2-1 -1 -1 -1 -1 -1 -1整串abacaba看起来好像有点规律但确实不能由某个更短的串重复至少2次构成。具体为什么下面用next数组算一遍就清楚了。2.2 这道题真正在考什么这个题面看起来简单背后有四个考点求每个前缀的最长相等前后缀长度这正是KMP预计算阶段做的事用nxt[L]推出候选周期 d L - nxt[L]判断是否满足 L % d 0 且 d L决定该前缀能否由更短串重复构成处理边界条件L1、整个串本身不是循环串时都要输出-1。暴力做法会超时得很惨。比如对每个前缀枚举所有可能因子d再逐个位置比较最坏情况是O(n^2)n到10^6时完全跑不动。所以这道题想考察的就是你能不能想到用KMP的next数组把判定压缩到O(n)。2.3 为什么“next数组”是解题钥匙KMP算法里有一步是预处理模式串的next数组匹配阶段靠它实现失配后不回退主串指针。而next数组本身蕴含的信息比“失配回退”更丰富——它记录的是每个前缀的“最长相等前后缀”长度这个信息天然可以用于周期判定。换句话说这道题表面考的是循环节实际考的是你对next数组本质的理解。如果你只是单纯背模板不知道next数组里存的是什么这道题基本做不出来。3. KMP的next数组两种定义与一次手算推演3.1 next数组的本质最长相等前后缀先说清楚什么是“最长相等前后缀”。对于一个字符串prefix它的前缀和后缀不能包含字符串自身。比如abacab最长相等前后缀是ab长度为2。next数组记录的就是这个信息但不同教科书定义不同这是很多考生搞混的根源。我统一采用下面的定义Anxt[i] 表示字符串前 i 个字符即 s[0..i-1] 的最长相等前后缀长度。 nxt[0] -1作为递推起点。失配回退时直接 j nxt[j] 就能跑代码不容易记混。至于另一种定义B后面我会专门讲区别。3.2 手算“abacaba”的完整过程设模式串 p abacaba我们用定义A手算nxt数组。初始时nxt[0] -1 i 0, j -1KMP预计算的递推过程如下第1步j -1进入基础分支。 i 1, j 0, nxt[1] 0 第2步i1, j0比较 p[1]b 与 p[0]a不等。 j nxt[0] -1 第3步j -1进入基础分支。 i 2, j 0, nxt[2] 0 第4步i2, j0比较 p[2]a 与 p[0]a相等。 i 3, j 1, nxt[3] 1 第5步i3, j1比较 p[3]c 与 p[1]b不等。 j nxt[1] 0 第6步i3, j0比较 p[3]c 与 p[0]a不等。 j nxt[0] -1 第7步j -1进入基础分支。 i 4, j 0, nxt[4] 0 第8步i4, j0比较 p[4]a 与 p[0]a相等。 i 5, j 1, nxt[5] 1 第9步i5, j1比较 p[5]b 与 p[1]b相等。 i 6, j 2, nxt[6] 2 第10步i6, j2比较 p[6]a 与 p[2]a相等。 i 7, j 3i到达串尾结束。最终得到nxt [-1, 0, 0, 1, 0, 1, 2]注意nxt[7]也在构建过程中算出来了等于3它表示整个串abacaba的最长相等前后缀是aba长度为3。3.3 两种next定义的坑与换算很多教材用的是另一种定义next[i] 表示 s[0..i] 的最长相等前后缀长度。这种情况下abacaba的next数组是next [0, 0, 1, 0, 1, 2, 3]两种定义有个简单的换算关系定义B的next[i]等于定义A的nxt[i1]。| 下标i | 字符 | 定义Anxt[i] | 定义Bnext[i] | | 0 | a | -1 | 0 | | 1 | b | 0 | 0 | | 2 | a | 0 | 1 | | 3 | c | 1 | 0 | | 4 | a | 0 | 1 | | 5 | b | 1 | 2 | | 6 | a | 2 | 3 | | 7 | 串尾 | 3 | 无 |做题