本篇将大量摘自 OI-Wiki 本人当初学的时候也是看到这几篇博客才顿悟的,自觉这部分讲的不会比原作者更好 author: Ir1d, LeoJacob, Xeonacid, greyqz, StudyingFather, Marcythm, minghu6, Backl1ght
又称模式匹配(pattern matching)。该问题可以概括为「给定字符串
和
,在主串
中寻找子串
」。字符
称为模式串 (pattern)。
类型:
暴力做法:
简称 BF (Brute Force) 算法。该算法的基本思想是从主串
的第一个字符开始和模式串
的第一个字符进行比较,若相等,则继续比较二者的后续字符;否则,模式串
回退到第一个字符,重新和主串
的第二个字符进行比较。如此往复,直到
或
中所有字符比较完毕。
在最好情况下,BF 算法匹配成功时,时间复杂度为
;匹配失败时,时间复杂度为
。
在最坏情况下,每趟不成功的匹配都发生在模式串的最后一个字符,BF 算法要执行
次比较,时间复杂度为
。
字符串哈希是字符串模式匹配中的一个经典做法,具体概念在上一章 “0x14 哈希” 中讲过了
这里提一下字符串哈希的经典应用:
次失配的字符串匹配
给定一个长度为
的字符串
,其 前缀函数 被定义为一个长度为
的数组
。
其中
的定义是:
有一对相等的真前缀与真后缀:
和
,那么
就是这个相等的真前缀(或者真后缀,因为它们相等)的长度,也就是
;
就是其中最长的那一对的长度;
。
简单来说
就是,子串
最长的相等的真前缀与真后缀的长度。
用数学语言描述如下:
特别地,规定
。
朴素做法就是暴力枚举,对于当前求得前缀
,让
从
到
枚举到第一个前后缀匹配的长度
时间复杂度为:
第一个优化
观察易得 相邻的前缀函数值至多增加
当取一个尽可能大的
时,必然要求新增的
也与之对应的字符匹配,即
, 此时
所以当移动到下一个位置时,前缀函数的值要么增加一,要么维持不变,要么减少。
最终比较次数会减少到
次,总时间复杂度为
第二个优化
第一个优化中讨论了计算
时的最好情况
,此时
,现讨论当
如何跳转?
失配时,我们希望找到对于子串
,仅次于
的第二长度
,使得在位置
的前缀性质仍得以保持,也即
:
如果我们找到了这样的长度
,那么仅需要再次比较
和
。如果它们相等,那么就有
。否则,我们需要找到子串
仅次于
的第二长度
,使得前缀性质得以保持,如此反复,直到
。如果
,则
。
观察上图可以发现,因为
,所以对于
的第二长度
,有这样的性质:
也就是说
等价于子串
的前缀函数值,即
。同理,次于
的第二长度等价于
的前缀函数值,
显然我们可以得到一个关于
的状态转移方程:
最终代码如下:
int ne[SIZE];
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && a[j + 1] != a[i]) j = ne[j];
if (a[i] == a[j + 1]) j ++ ;
ne[i] = j;
}
前缀函数的经典应用
该任务是前缀函数的一个典型应用,利用计算好的前缀函数,我们可以快速完成字符串的模式匹配
因为定义的相似性,求解主串与模式串匹配的过程,就是求解当前主串枚举到的子串中后缀与匹配串前缀的最大匹配长度
如果此时长度刚好等于匹配串的长度,则说明匹配成功
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && (j == n || b[i] != a[j + 1])) j = ne[j];
if (b[i] == a[j + 1]) j ++ ;
f[i] = j;
// if (f[i] == n) //此时就是 A 在 B 中的某一次出现
}
由于每个阶段,
变化的浮动为上一轮的
到
,且同时每个阶段
至多增加
,因此
在整个过程中,其 减少的次数小于等于增加的次数,算上增加和减少
的总变化次数至多为:
,易得 KMP 的时间复杂度为
字符串周期的定义:
,都有
,则称
为字符串
的周期
字符串border的定义:
,若
,则称
长度为
的前缀是
的 border
显然
是
的周期,利用该性质以及前缀函数的定义,可以得到
的所有 border 长度,即:
所以根据前缀函数可以在
的时间内计算出
的所有周期
其中
为最长的 border 长度,因此
为
的最小周期
考虑位置
的前缀函数值
。根据定义,其意味着字符串
一个长度为
的前缀在位置
出现并以
为右端点,同时不存在一个更长的前缀满足前述定义。与此同时,更短的前缀可能以该位置为右端点。
容易看出,我们遇到了在计算前缀函数时已经回答过的问题:给定一个长度为
的前缀,同时其也是一个右端点位于
的后缀,下一个更小的前缀长度
是多少?该长度的前缀需同时也是一个右端点为
的后缀。
因此以位置
为右端点,有长度为
的前缀,有长度为
的前缀,有长度为
的前缀,等等,直到长度变为
。故而我们可以通过下述方式计算答案。
vector<int> ans(n + 1);
for (int i = 1; i <= n; i ++ ) ans[pi[i]]++;
for (int i = n; i >= 1; i -- ) ans[pi[i - 1]] += ans[i];
for (int i = 1; i <= n; i ++ ) ans[i]++;
字符串的最小表示法:最小表示法是求与某个字符串 循环同构 的所有字符串中,字典序最小的
如何在
的时间内求出字符串的最小表示
类似 循环同构 的问题,第一时间想到 破环成链,将数组整体复制接到后面,然后寻找长度为
的最小字典序
先枚举起点,然后暴力挨个比较的做法,时间复杂度为
,对于本题的数据规模完全是 ok 的
这里介绍一个线性的做法:
考虑对于一对字符串
, 它们在原字符串
中的起始位置分别为
, 且它们的前
个字符均相同,即
不妨先考虑
的情况,我们发现起始位置下标
满足
的字符串均不能成为答案。因为对于任意一个字符串
(表示以
为起始位置的字符串)一定存在字符串
比它更优。
所以我们比较时可以跳过下标
, 直接比较
这样对于每个指针都只会向后位移,因此时间复杂度为
算法流程
为
,
为
与
两个循环同构串
个字符后仍然相等,说明
有更小的循环元,且该循环元已扫描完毕,
即为最小表示
与
处发现不相等:
,令
若此时
,则令
,令
若此时
,则令
或
,则
即为最小表示,否则重复第二步
int n = strlen(s + 1);
for (int i = 1; i <= n; i ++ ) s[n + i] = s[i];
int i = 1, j = 2, k;
while (i <= n && j <= n)
{
for (k = 0; k < n && s[i + k] == s[j + k]; k ++ );
if (k == n) break; // 形如catcat,它的循环元已扫描完成
if (s[i + k] > s[j + k])
{
i = i + k + 1;
if (i == j) i ++ ;
}
else
{
j = j + k + 1;
if (i == j) j ++ ;
}
}
ans = min(i, j);
一个字符串的前缀是从第一个字符开始的连续若干个字符,例如
共有
个前缀,分别是
,
,
,
,
。
我们希望知道一个
位字符串
的前缀是否具有循环节。
换言之,对于每一个从头开始的长度为
(
)的前缀,是否由重复出现的子串
组成,即
(
重复出现
次,
)。
如果存在,请找出最短的循环节对应的
值(也就是这个前缀串的所有可能重复节中,最大的
值)。
输入格式
输入包括多组测试数据,每组测试数据包括两行。
第一行输入字符串
的长度
。
第二行输入字符串
。
输入数据以只包括一个
的行作为结尾。
输出格式
对于每组测试数据,第一行输出 Test case #
和测试数据的编号。
接下来的每一行,输出具有循环节的前缀的长度
和其对应
,中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。
数据范围
输入样例:
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例:
Test case #1
2 2
3 3
Test case #2
Test case #3
2 2
6 2
9 3
12 4
根据我在上文中的有关 “前缀函数求字符串的周期” 内容继续
对于一个字符串border长度,其最长为
,因此最小正周期为
综上,如果当前字符串的最小正周期
能够整除当前字符串的长度
,则他一定存在循环元
根据该理论,输出结果即可
void solve()
{
scanf("%s", str + 1);
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && str[i] != str[j + 1]) j = ne[j];
if (str[i] == str[j + 1]) j ++ ;
ne[i] = j;
}
for (int i = 2; i <= n; i ++ )
if (i % (i - ne[i]) == 0 && i / (i - ne[i]) > 1)
printf("%d %d\n", i, i / (i - ne[i]));
puts("");
}