用KMP判断最小循环节

#include 
    
     #include 
     
      #include 
      
       using namespace std;char s[105];int f[105][105];int fail[105];int calc(int l, int r) {    fail[l] = fail[l + 1] = l;    for(int i = l + 1; i <= r; i++) {        int cur = fail[i];        while(cur != l && s[cur] != s[i]) cur = fail[cur];        if(s[cur] == s[i]) cur++;        fail[i + 1] = cur;    }    int len1 = r - l + 1, len2 = len1 - (fail[r + 1] - l);    int res = len1 + 3;    if(len1 % len2 == 0) {        res = f[l][len2 + l - 1] + 3;        if(len1 / len2 > 9) res++;        if(len1 / len2 > 99) res++;    }    return res;}int main() {    scanf("%s", s);    int n = strlen(s);    memset(f, 0x3f, sizeof(f));    for(int i = 0; i < n; i++) f[i][i] = 1;    for(int len = 1; len <= n; len++) {        for(int l = 0, r = len - 1; r < n; l++, r++) {            for(int i = l; i < r; i++)               f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);            f[l][r] = min(f[l][r], calc(l, r));        }    }    printf("%d\n", f[0][n - 1]);    return 0;}