洛谷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;
}