字符环

题意

两个字符串首尾相连形成字符环，求两环的最长连续公共字符串长度。

思路

把每个环复制为两倍长度，任意跨越原串末尾的连续片段都会变成双串中的普通子串。设 dp[i][j] 为两个双串分别以第 $i,j$ 个字符结尾的最长公共后缀，字符相等时从左上角状态加一，否则为零。

公共片段不能绕环超过一整圈，因此每个状态取不超过两原串较短长度的值。代码用两行数组滚动保存 DP。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16first, second = input().split()
first_twice = first + first
second_twice = second + second
maximum_length = min(len(first), len(second))
previous = [0] * (len(second_twice) + 1)
answer = 0

for first_character in first_twice:
    current = [0] * (len(second_twice) + 1)
    for index, second_character in enumerate(second_twice, 1):
        if first_character == second_character:
            current[index] = min(previous[index - 1] + 1, maximum_length)
            answer = max(answer, current[index])
    previous = current

print(answer)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;



char s1[1000];
char s2[1000];
char tmp[1000];
int main(){
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int l1  = strlen(s1+1);
    int l2  = strlen(s2+1);
    int i,j;
    for (i=1;i<l1;i++){
        s1[l1+i] = s1[i];
    }
    for (i=1;i<l2;i++){
        s2[l2+i] = s2[i];
    }

    if(l1 < l2){
        swap(s1,s2);
        swap(l1,l2);
    }

    for(i=l2;i>=1;i--){
        for(j=1;j<=l2+l2-i;j++){
            memset(tmp,0,sizeof(tmp));
            strncpy(tmp,s2+j,i);
            //printf("%d %s\n",i,tmp);
            if( strstr(s1+1,tmp)!=NULL){
                //printf("%s",s2+j);
                printf("%d",i);
                return 0;
            }
        }
    }
    printf("0");
    return 0;
}

复杂度

设两串长度为 $n,m$ ，双串 DP 时间复杂度为 $O(nm)$ ，滚动数组空间复杂度为 $O(m)$ 。

总结

环上的连续子串问题常先把环展开成双倍字符串，再套线性字符串算法。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结