洛谷-P1944 最长括号匹配（字符串动态规划）

题目描述

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

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

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

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

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

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

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

输入格式

输入一行，为一个仅由()[]组成的非空字符串。

输出格式

输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。

输入输出样例

输入 #1

([(][()]]()

输出 #1

[()]

输入 #2

())[]

输出 #2

()

说明/提示

【数据范围】

对20%的数据，字符串长度<=100.

对50%的数据，字符串长度<=10000.

对100%的数据，字符串长度<=1000000.

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s; cin >> s;
    int n = s.size();
    vector<int> d(n, 0);
    int res = 0, pos = 0;
    for (int i = 1; i < n; ++i) {
        if ( i > d[i - 1] && ((s[i] == ')' && s[i - 1 - d[i - 1]] == '(') 
            || (s[i] == ']' && s[i - 1 - d[i - 1]] == '[')) ) {
            d[i] = d[i - 1] + 2 + (i >= 2 + d[i - 1 ] ? d[i - 2 - d[i - 1]] : 0);
            if (d[i] > res) {
                res = d[i];
                pos = i;
            }
        }
    }
    cout << (pos - res + 1 >= 0 ? s.substr(pos - res + 1, res) : "") << endl;

    return 0;
}

这道题是LeetCode 32的扩展，用d[i]表示以s[i]为结尾的最长有效括号长度，那么d[i - 1]表示以s[i-1]结尾的最长有效括号长度，那么如果和s[i - 2 - d[i - 1]]匹配，那么就可以更新长度，另外需要考虑涉及下标的时候，要保证下标在合理的范围内。