P1944 最长括号匹配

P1944 最长括号匹配

题意:

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

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

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

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

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

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

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

数据范围:

字符串长度 \(\le 1000000\)

思路:

定义 \(dp[i]\) 为以 \(i\) 结尾的最长的匹配的括号长度

因为如果多个括号外部匹配内部一定匹配，所以 \(s[i - dp[i - 1] - 1]\) 就是与当前 \(i\) 匹配的位置，如果匹配的话，就转移，但是注意，当前匹配，如果之前的也匹配，就也要加上去。

实现:

#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
const int N = 1e6 + 5;
char s[N];
int dp[N];
int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 2; i <= n; i++)
    {
        if (s[i] == ')')
        {
            if (s[i - dp[i - 1] - 1] == '(')
                dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
        }
        else if (s[i] == ']')
            if (s[i - dp[i - 1] - 1] == '[')
                dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
    }
    int flag, last = 0;
    for (int i = 1; i <= n; i++)
        if (dp[i] > last)
        {
            flag = i;
            last = dp[i];
        }

    for (int i = flag - dp[flag] + 1; i <= flag; i++)
        printf("%c", s[i]);

    return 0;
}