[BOI2009]Radio Transmission 无线传输

首先求出next数组,可知字符串最长公共前后缀为数组最后一个元素。

将前后缀中的重叠部分拿出来合并比较,我们不难发现最小重复单元就是字符串长度和字符串最长公共前缀和的差值。

例如:

项目内容
原串CABCABCA
最长公共前缀CABCA
最长公共后缀CABCA

例中重叠部分是CA,而两串所“空缺”的地方正好就是一个完整的重复单元。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;

int l;
int len;
int pi[MAXN];
string s;

int main() {
    ios::sync_with_stdio(false);

    cin >> l >> s;
    len = s.length();

    int j = 0;
    for ( int i = 1; i < len; ++i ) {
        j = pi[i - 1];

        while ( j && s[j] != s[i] )
            j = pi[j - 1];
        
        if ( s[j] == s[i] )
            ++j;

        pi[i] = j;
    }

    cout << l - pi[l - 1] << endl;

    return 0;
}
Last modification:October 1st, 2019 at 07:17 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment