题解P4391 [BOI2009]Radio Transmission 无线传输

Kalium · 2021-02-25 18:22:10 · 个人记录

P4391 [BOI2009]Radio Transmission 无线传输题解

题意：

告诉你一个串 A，它是由 B 连着写多次得到的子串，求 B 串的最小长度

思路：

前置芝士：KMP

这题很巧妙的运用了 KMP

我们想想，与其直接求 B 串的最小长度，不如去求 A 串最多能被减多少长度

那么我们仔细想想 nxt_i 的概念，是前缀和后缀共有的最大长度

注意 共有 这个词

共有的话，意思就是说，我们只需复制 1 次即可得到相同的吧

那么对于不在共有之间的就没办法了，再复制一遍吧

所以答案就是 n - nxt_n

还是很好做的

代码：

CODE

#include <iostream>
#include <cstdio>
#include <cstring>

const int N = 1e6 + 7;

using namespace std;

int len;

char s[N];

int nxt[N];

inline void pre() {
    int j = 0;

    for (int i = 2; i <= len; i ++) {
        while (j && s[j + 1] != s[i])
            j = nxt[j];

        if (s[j + 1] == s[i])
            j ++;

        nxt[i] = j;
    }
}

int main() {
    cin >> len;
    scanf("%s", s + 1);

    pre();

    cout << len - nxt[len] << endl;

    return 0;
}