算法|题解

计蒜客 – 重复的密文

jxtxzzw · 3月10日 · 2020年 · · 196次已读

计蒜客 – 重复的密文

蒜头君收到了一串密文,但是由于接收器坏了,他不停的重复接收,终于,蒜头君把插头拔了,机器停止了,但是蒜头君已经收到了一个很长字符串,它是由某个原始串不停的重复形成了,因为断电,最后一遍也不一定是完整的。蒜头君现在想知道这个原始串的最短可能长度是多少。

输入格式

第一行输入一个正整数 $L(1 < L \leq 10^6)$,表示这个字符串的长度。

第二行输入一个字符串,全部由小写字母组成。

8
cabcabca

输出格式

答案输出,输出最短的可能长度。

3

这道题是求 KMP 的最小循环节。

仔细观察 next[] 数组,可以发现,如果出现循环,那么除了第一个循环节的值都是 $0$,从第二个循环节开始,包括最后一个,都是递增的,而且记录了最长公共前缀。

所以利用 KMP 求出 next[] 数组,L - next[L] 就是答案。

注:next[] 数组也常被称作 fail[] 数组,失败链接值。

#include <bits/stdc++.h>

// 为了编程方便,next 数组下标从 1 开始,所以 string 也要下标从 1 开始,所以封装了一个 read
char* read(int length) {
    char* s = (char*)malloc(sizeof(char) * (length + 2));
    for (int i = 1; i <= length; i++) {
        char c;
        scanf("%c", &c);
        s[i] = c;
    }
    s[length + 1] = '\0';
    return s;
}

// 以字符串 t 求 next 数组,n 为字符串长度
int* getNext(const char* t, int length) {
    int* next = (int*)malloc(sizeof(int) * (length + 1));
    next[1] = 0;
    for(int i = 2; i <= length; i++) {
        int j = next[i - 1];
        while(t[j + 1] != t[i] && j > 0) {
            j = next[j];
        }
        if(t[j + 1] == t[i]) {
            next[i] = j + 1;
        } else {
            next[i] = 0;
        }
    }
    return next;
}

void print(const char * t, const int* next, int n) {
    for (int i = 1; i <= n; i++) {
        printf("%c%c", t[i], i == n ? '\n' : '\t');
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", next[i], i == n ? '\n' : '\t');
    }
}

int main() {
    int n;
    scanf("%d\n", &n);
    char* t = read(n);
    int* next = getNext(t, n);
//    print(t, next, n);
    printf("%d\n", n - next[n]);
}

说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
  订阅评论动态  
提醒