最长公共 / 对称字串

求最长对称字串是求最长公共子串的变形.. (๑˘ ˘๑)

最长公共子串 Longest Common Subsequence

子串有别于子序列, 子序列的字符可以不连续,子串则必须连续
题为求　最长对称子串，　实际可以转化成求最长公共子串
对给定的字符串，本题要求你输出最长对称子串的长度。
例如，给定"Is PAT&TAP symmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。

输出格式：
在一行中输出最长对称子串的长度。

输入样例: Is PAT&TAP symmetric?
输出样例: 11

分析

明确是对称子串，相当于求某个字符串和其逆序的公共子串，到此将求最长对称子串转为求最长公共子串。

思路是动态规划, 用一个表来记录中间过程
L[i, j] 表示两个字符串a, b在比较 a[0 ~ i], b[0 ~ j] 时的最长公共子序列　
有状态转移方程：

L[i, j] = 
0                               某一个串长度为0时
L[i - 1, j - 1] + 1             a[i] == b[j]
max{L[i, j - 1], L[i - 1, j]}   a[i] != b[j]

留意这里的i,j是指子序列的长度,而非要比较的两个string的下标
而对于最长公共 子串 可以推理得状态方程

L[i, j] =
0                       某个串长度为0或a[i] != b[j]
L[i - 1, j - 1] + 1     a[i] == b[j]

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f, maxN = 1005;
int N, M;
char sa[maxN], sb[maxN];
int dp[maxN][maxN];


int main() {
    // freopen("data.in", "r", stdin);
    cin.getline(sa, maxN);
    int la = strlen(sa), lb = la;
    for (int i = 0; i < la; ++i)
        sb[i] = sa[la - 1 - i];

    for (int i = 0; i < la; ++i)
        dp[0][i] = dp[i][0] = 0;

    int ans = -inf;
    for (int i = 1; i <= la; ++i) {
        for (int j = 1; j <= lb; ++j) {
            if (sa[i - 1] == sb[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = 0;
            ans = max(ans, dp[i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}