题解 P1435 【回文字串】

· · 题解

窝写这篇题解是给你们安利一个新科技（雾），主要是因为没有找到LCS的模板题，只能在这发题解

这是学长想出来的w

我们都知道是把这个序列翻转之后求两个序列的LCS是吧...

那么重点肯定在LCS！

先来看看这道题

给你两个小写字母串 s1 ， s2 ，求它们两个的LCS（最长公共子序列）

对于 70%的数据，|s1| , |s2|<= 2000

这个数据是傻逼，只要你会LCS的dp

对于 100%的数据，|s1| <= 3 * 10^6 ， |s2| <= 2000

这个数据是傻逼，只要你会序列自动机

好吧我们现在都不会那个什么序列自动机，有什么办法做呢

先看回那个70%数据的那个dp...

状态：

转移方程： $dp[i][j]$ $=$ $max(dp[i-1][j] , dp[i][j - 1],dp[i-1][j-1]+[s1[i]==s2[j]])

窝看你的数组开不下呀！

因为|s1|太大了！

要不把LCS的长度扔进去状态，然后把那个占空间的s1当成dp数组里存的值？

那么我们的状态变成了

dp[i][j]$ 代表 $s2$前$i$个字符构成的子串与$s1$ 的前$dp[i][j]$个字符构成的子串的LCS长度为$j

怎么转移呢？

定义next[i][c]，代表找的一个最小的j，满足j>i并且s1[j] ==c的j

这个能随便算...

然后转移方程成了这样：

dp[i][j]$ $=$ $min(dp[i+1][j] , next[dp[i+1][j+1]][s2[i+1]])

时间复杂度O(min(|s1|,|s2|) ^ 2)，空间复杂度O(26 * |s1|+ min(|s1|,|s2|) ^ 2)

然后你会发现这个方法可以降低很多个O(N^2)的关于子序列的dp复杂度，只要能快速算next数组