回文子串

题意

输出所有长度至少为 $2$ 的回文子串，先按长度升序，再按起点升序。

思路

设 is_palindrome[left][right] 表示该闭区间是否回文。若两端字符相同，且中间区间也是回文，则当前区间回文；单字符对角线先设为真。外层按子串长度枚举、内层按起点枚举，天然满足输出顺序。

DP 状态示意

下表展示 abba 的关键状态，单元格表示对应子串是否回文：

子串	`bb`	`abba`
两端字符相同	是	是
内部区间回文	单字符	`bb`
结果	是	是

先确认短区间，再扩展到更长区间，这正是状态依赖方向。

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20import sys

text = input().strip()
length = len(text)
is_palindrome = [[False] * length for _ in range(length)]
answer = []

for index in range(length):
    is_palindrome[index][index] = True

for substring_length in range(2, length + 1):
    for start in range(length - substring_length + 1):
        end = start + substring_length - 1
        if text[start] == text[end] and (substring_length == 2 or is_palindrome[start + 1][end - 1]):
            is_palindrome[start][end] = True
            answer.append(text[start : end + 1])

sys.stdout.write("\n".join(answer))
if answer:
    sys.stdout.write("\n")

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#include <cstdio>
#include <cstring>

char s[1000];
char tmp[1000];

bool is_hui_wen(){
    int len =  strlen(tmp);
    int mid = len /2;
    int i,j;
    for (i=0;i<mid;i++){
        if( tmp[i] != tmp[len-i-1]){
            return false;
        }
    }
    return true;
}
int main(){
    scanf("%s",s+1);
    int len = strlen(s+1);
    int i,j;
    for(i=2;i<=len;i++){
        for (j=1;j<=len-i+1;j++){
            memset(tmp,0,sizeof(tmp));
            strncpy(tmp,s+j,i);
            //printf("%s\n",tmp);
            if( is_hui_wen())
                printf("%s\n",tmp);
        }
    }
    return 0;
}

复杂度

状态数为 $O(n^2)$ ，时间和空间复杂度均为 $O(n^2)$ ，不含输出本身。

总结

回文区间的两端相等与内部回文构成了标准区间 DP 递推。

代码

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#include <cstdio>
#include <cstring>

char s[1000];
char tmp[1000];

bool is_hui_wen(){
    int len =  strlen(tmp);
    int mid = len /2;
    int i,j;
    for (i=0;i<mid;i++){
        if( tmp[i] != tmp[len-i-1]){
            return false;
        }
    }
    return true;
}
int main(){
    scanf("%s",s+1);
    int len = strlen(s+1);
    int i,j;
    for(i=2;i<=len;i++){
        for (j=1;j<=len-i+1;j++){
            memset(tmp,0,sizeof(tmp));
            strncpy(tmp,s+j,i);
            //printf("%s\n",tmp);
            if( is_hui_wen())
                printf("%s\n",tmp);
        }
    }
    return 0;
}

目录

题意

思路

DP 状态示意

Python代码

C++代码

复杂度

总结

代码

复杂度

总结