BOI2009 Radio Transmission 无线传输

发表于 更新于 分类于

$Problem’s$ $Website$

BOI2009 Radio Transmission 无线传输

$Solution$

  • 这道题会详细地解释$KMP$算法中的$next$数组(下文写作$nxt$)，可以配合我的另外一篇辣鸡题解进行学习。

长话短说，说一下$nxt$数组。

在模式串中(就是短的字符串)，$nxt[i]$ $\le$ $i$ 并且 $str[i] == str[nxt[i]]$ 并且在 $j != 1$时应满足$str[1]$ ~ $str[nxt[i] - 1]$ $=$ $str[i - nxt[i] +1]$ ~ $str[i - 1]$，就是它们的前缀相等。

关于这题如何求最小周期

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
int n;
char s[1000010];
int nxt[1000010];
int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    int j =0;
    for(re int i = 2; i <= n; ++i) {
        while(j && s[j + 1] != s[i])
            j = nxt[j];
        if(s[j + 1] == s[i])
            ++j;
        nxt[i] = j;
    }
//    for(re int i = 1; i <= n; ++i)
//    	printf("%d ", nxt[i]);
    printf("%d\n", n - nxt[n]);
    return 0;
}

$rp++$