洛谷P1944 最长括号匹配 题解

题意：对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：

1.(),[]是括号匹配的字符串。

2.若A是括号匹配的串，则(A),[A]是括号匹配的字符串。

3.若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。

例如：(),[],([]),()()都是括号匹配的字符串，而][,[(])则不是。

字符串A的子串是指由A中连续若干个字符组成的字符串。

例如，A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。空串是任何字符串的子串。

似乎可以用栈模拟，但是这个太没劲了，考虑dp

设 $dp[i]$ 表示以 $s[i]$ 结尾的最长括号匹配长度

显然当 $s[i]$ 为左括号时 $dp[i]=0$

当 $s[i]$ 为右括号时，$dp[i]$ 一定与 $dp[i-1]$ 有关

容易发现 $s[i-dp[i-1]]$ 是 $dp[i-1]$ 的起始字符

则当 $s[i-dp[i-1]-1]$ 与 $s[i]$ 合法匹配时，有

$dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]$

这里的 $dp[i-dp[i-1]-2]$ 只需要一个例子就好理解了

[]([])
123456

假设此时为 $dp[5]=2$ ，对于以 $s[5]$ 结尾的最长括号匹配显然是[]

然后到了 $dp[6]=6$ ，注意到此时 $s[3]$ 被合法利用了，

这样就造成了 $s[3]$ 之前的 $dp[6-dp[5]-2] = dp[2]$ 被重新利用

应该很好理解了

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)
int n,ans,dp[N],id;
char s[N];
signed main()
{
    scanf("%s",(s+1));n=strlen(s+1);
    for(int i=2; i<=n; i++)
    {
        if(s[i]=='('||s[i]=='[')continue;
        else
        {
            if(s[i]==')'&&s[i-dp[i-1]-1]=='('||
            s[i]==']'&&s[i-dp[i-1]-1]=='[')
            {
                dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2];
                if(dp[i]>ans)ans=dp[i],id=i;
            }
        }
    }
    for(int i=id-ans+1; i<=id; i++)
        putchar(s[i]);
    puts("");
    return 0;
}