算法|题解

计蒜客 – 首尾相接

凝神长老 · 3月15日 · 2020年 · · · 773次已读

计蒜客 – 首尾相接

蒜头君有两个字符串 $S_1$ 和 $S_2$,蒜头君想把 $S_1$ 接到 $S_2$ 后面。因为 $S_1$ 前面有一些字符和 $S_2$ 后面的一些字母一样,所以蒜头君在连接的时候就没必要重复了,比如 $S_1$ 为 cdefgh,$S_2$ 为 abcde,那么 cde 这部分就是最长的重复部分,蒜头君可以将这两个串连接为 abcdefgh。现在,给你串 $S_1$ 和串 $S_2$,请你帮蒜头君找出最长重复部分的长度。

输入格式

共两行,每行一个字符串,由小写字母构成,第一行表示串 $S_1$,第二行表示串 $S_2$。

$(1\leq |S_1|,|S_2|\leq 50000)$

riemann
marjorie

输出格式

答案输出在一行,先输出重复的字符串,再输出其长度,中间以空格隔开。若该串为空,只需输出 $0$。

rie 3

这题用 KMP 或者拓展 KMP 都能做。

直接用 KMP 好了,简单点。

首先把 $s1$ 和 $s2$ 依次拼接,然后对拼接成的字符串做一次 getNext(),该数组最后一个元素的值就是答案,因为它表示它所对应的字符之前有多少个,与该字符串开头的那么多个是一样的,这显然与题目要求的重复部分是相同的,因此直接输出 next[len3] 即可,对应的字符串就是开头的那么多个。

#include <bits/stdc++.h>

#define MAX_LEN 50007

// 以字符串 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;
}

// 拼接两个字符串
char* concat(const char* s1, const char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char* s3 = (char*)malloc(sizeof(char) * (len1 + len2 + 2));
    strncpy(s3 + 1, s1, len1);
    strncpy(s3 + 1 + len1, s2, len2);
    s3[1 + len1 + len2] = '\0';
    return s3;
}


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() {
    char s1[MAX_LEN], s2[MAX_LEN];
    scanf("%s%s", s1, s2);
    char* s3 = concat(s1, s2);
    int len3 = strlen(s3 + 1);
    int* next3 = getNext(s3, len3);
//    print(s3, next3, len3);
    int ans = next3[len3];
    if (ans > 0) {
        for (int i = 0; i < ans; i++) {
            printf("%c", s1[i]);
        }
        printf(" ");
    }
    printf("%d", ans);
}
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论