侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【KMP算法】周期

GabrielxD
2023-02-27 / 0 评论 / 0 点赞 / 205 阅读 / 2,556 字
温馨提示:
本文最后更新于 2023-02-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
本文原作者:yxc

题目

141. 周期 - AcWing题库


一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab 共有 55 个前缀,分别是 aababaabaaabaab

我们希望知道一个 NN 位字符串 SS 的前缀是否具有循环节。

换言之,对于每一个从头开始的长度为 iii>1i>1 )的前缀,是否由重复出现的子串 AA 组成,即 AAAAAAA…AAA 重复出现 KK 次, K>1K>1 )。

如果存在,请找出最短的循环节对应的 KK 值(也就是这个前缀串的所有可能重复节中,最大的 KK 值)。

输入格式

输入包括多组测试数据,每组测试数据包括两行。

第一行输入字符串 SS 的长度 NN

第二行输入字符串 SS

输入数据以只包括一个 00 的行作为结尾。

输出格式

对于每组测试数据,第一行输出 Test case # 和测试数据的编号。

接下来的每一行,输出具有循环节的前缀的长度 ii 和其对应 KK ,中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围

2N10000002 \le N \le 1000000

输入样例:

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

解题

方法一:KMP算法

思路

KMP算法及其原理在此不做说明,详见:KMP算法

以下思路来自:y总的视频讲解

设有一段字符串 s[1n]s[1\dots n] ,那么通过KMP算法构造出的 nextsnexts 数组中 nexts[n]nexts[n]s[1n]s[1 \dots n]最长相等前后缀,把 s[1n]s[1 \dots n] 复制一份并向后平移使得两串最长相等前后缀重合,如图:

image-20230227102953362

由于 ss' 是由 ss 平移来的,所以有 s[1nnexts[n]]=s[1nnexts[n]]s[1 \dots n - nexts[n]] = s'[1 \dots n - nexts[n]] (以下称 nnexts[n]n - nexts[n]TT):

image-20230227103309113

又由于前后缀 s[Tn]s[T \dots n]s[1nexts[n]]s'[1 \dots nexts[n]] 相等,故有 s[1T]=s[T2T]s'[1 \dots T] = s[T \dots 2T]

image-20230227103545581

再由于 ss' 是由 ss 平移来的,所以 s[T2T]=s[T2T]s[T \dots 2T] = s'[T \dots 2T]

image-20230227103743022

由于前后缀 s[Tn]s[T \dots n]s[1nexts[n]]s'[1 \dots nexts[n]] 相等,所以 s[2Tn]=s[Tnexts[n]]s[2T \dots n] = s'[T \dots nexts[n]] (图中 PTPT):

image-20230227104113619

图中可以很明显的在 ss' 中看出 PTPTTT 的一个前缀,而 TTs[1n]s[1 \dots n] 的一个循环节[1]T=nnexts[n]T = n - nexts[n])。

证明 TT最小的一个循环节?

反证法:假设有 TT' 是一个更小的循环节(T<TT' < T),我们像刚才那样对齐,只不过对齐的是循环节 TT'

image-20230227105254332

如图 s[Tn]=s[12T+PT]s[T' \dots n] = s[1 \dots 2T' + PT'] ,这段相同的前后缀是由两个完成循环节 TT' 和一个循环节前缀 PTPT' 构成的,所以我们就找到了一对长度为 nTn - T' 的相等前后缀,又因为 T<TT' < T ,所以 nT>nTnT>nexts[n]n - T' > n - T \Longrightarrow n - T' > nexts[n] 。但是在KMP算法构造出的 nextsnexts 数组中,nexts[n]nexts[n] 表示的是所有的相等前后缀中长度最长的,现在却出现了更长的相等前后缀,所以 TT' 的存在会造成矛盾,故 T<TT' < T 不存在,也就是说 TT 一定是最小循环节

如果 TnT \mid n [2],根据题目要求(最小循环节,且长度能整除字符串长度), TT 就是答案。

但如果 TnT \nmid n 呢?是否存在一个稍微大一点的循环节 T(T>T)T' (T' > T) 使得 TnT' \mid n 呢?

如何证明当 Tn(T是最小循环节的长度)T \nmid n (T是最小循环节的长度) 时,不存在任何循环节 TT' 使得 TnT' \mid n

  • 证明性质:如果存在 T>TT'>T ,则 TT' 一定是 TT 的倍数(TTT \mid T'):

  • 反证法:假设 T(T>TTT)\exist T'(T' > T 且 T \nmid T') [3] ,设 d=gcd(T,T)d = \gcd(T, T')TTdTdTd<T\because T \nmid T \,\, \therefore d \ne T \,\,\,\, 又\because d \mid T \,\, \therefore d < T 。此时如果能证明 dd 也是一个循环节,那么就存在矛盾(存在更小的循环节比 TT 小),就能反证不能存在这样的 TT'

    • 证明 dd 也是一个循环节就是要证明 i,si=si+d\forall{i}, s_i = s_{i + d} [4]

    • 根据裴蜀定理d=xTyTd = xT - yT' ,那么(这段建议去看y总的视频讲解):

      i,si=si+T=si+2T==si+xT=si+xTT=si+xT2T==si+xTyT=si+d\forall{i}, s_{i} = s_{i + T} = s_{i + 2T} = \dots = s_{i + xT} = s_{i + xT - T'} = s_{i + xT - 2T'} = \dots = s_{i + xT - yT'} = s_{i + d}

    • dd 是一个循环节得证。

  • 此时就找到了一个更小的循环节 d(d<T)d (d < T) ,与 TT 存在矛盾,所以不存在 T(T>TTT)T'(T' > T 且 T \nmid T')

所以 TT' 必然是 TT 的倍数,也就是说所有循环节长度都是最小循环节长度的倍数,当 TnT \nmid n 时,TT 的所有倍数 TT' 就更不能整除 nn 了,也就是说:只要最小循环节不能整除 nn ,那么所有的循环节都不能整除 nn ,就一定无解

注意:Java一个case一个case输出会TLE,用 StringBuilder 拼接完后一起输出。

参考:AcWing 141. 周期(蓝桥杯集训·每日一题) - yxc

代码

字符串下标从 11 开始的写法(与思路相同):

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int cnt = 0;
        StringBuilder ans = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(in.readLine());
            if (n == 0) break;
            char[] s = ('\0' + in.readLine()).toCharArray();
            int[] nexts = new int[n + 1];
            for (int i = 2, j = 0; i <= n; ++i) {
                while (j > 0 && s[i] != s[j + 1]) j = nexts[j];
                if (s[i] == s[j + 1]) ++j;
                nexts[i] = j;
            }
            ans.append("Test case #").append(++cnt).append('\n');
            for (int i = 2; i <= n; ++i) {
                int p = i - nexts[i];
                if (i % p == 0 && i / p > 1) ans.append(i).append(' ').append(i / p).append('\n');
            }
            ans.append('\n');
        }
        System.out.print(ans);
    }
}

字符串下标从 00 开始的写法(处理稍微麻烦一点):

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int cnt = 0;
        StringBuilder ans = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(in.readLine());
            if (n == 0) break;
            char[] s = in.readLine().toCharArray();
            int[] nexts = new int[n];
            nexts[0] = -1;
            for (int i = 1, j = -1; i < n; ++i) {
                while (j >= 0 && s[i] != s[j + 1]) j = nexts[j];
                if (s[i] == s[j + 1]) ++j;
                nexts[i] = j;
            }
            ans.append("Test case #").append(++cnt).append('\n');
            for (int i = 1; i < n; ++i) {
                int len = i + 1, p = i - nexts[i];
                if (len % p == 0 && len / p > 1) ans.append(len).append(' ').append(len / p).append('\n');
            }
            ans.append('\n');
        }
        System.out.print(ans);
    }
}

  1. 这里的循环节定义与题目中不同,这里提到的循环节,整个字符串的长度可以不被其长度整除。 ↩︎

  2. \mid 是整除符号, aba \mid b 表示:bb 能被 aa 整除(或 aa 整除 bb),类似地, \nmid 为不能整除符号。 ↩︎

  3. 存在 T>TT' > TTTT \nmid T'↩︎

  4. 对于任意一个 ii 都有 si=si+ds_i = s_{i + d}↩︎

0

评论区