HDU 3746 – Cyclic Nacklace [KMP处理循环节]

点击打开hdu题目链接

Mean

有一个的串,让你在头部或者尾部增加最少的字符,使得这个头尾相接的串的循环节数>1.

Analyse

依然还是用KMP处理字符串的循环问题。如果前i个字符构成一个周期串,那么错位部分[fail[i], i]部分恰好是一个循环节,反过来也成立。本题的需要加几个特殊判断,如串长为1,或者fail[len]为0的情况。

Time Complexity

O(n)

C++ Code

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

const int maxn = 100010;
char s[maxn];
int fail[maxn], len;

void getFail(char *s, int *f) {
    f[0] = f[1] = 0;
    for(int i = 1; i < len; ++i) {
        int j = f[i];
        while(j && s[j]!=s[i]) j = f[j];
        f[i+1] = s[j]==s[i] ? j+1 : 0;
    }
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%s", s);
        len = strlen(s);
        getFail(s, fail);
        int t = len - fail[len];
        if(len == 1) puts("0");
        else if(fail[len] == 0) printf("%d\n", len);
        else if(len % t == 0) puts("0");
        else printf("%d\n", t - len % t);
    }
    return 0;
}

欢迎留言