【洛谷题库】最长括号匹配-题解

题意描述

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

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

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

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

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

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

例如，A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。

规定空串是任何字符串的子串。

现在问题来了，给你一个字符串，请求出它的最长匹配子串。

---

输入格式

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

---

输出格式

输出也仅有一行，为$s$的最长的括号匹配子串。

若有相同长度的子串，则请输出位置靠前的子串。

---

Input & Output ‘s examples

Input ‘s eg

([(][()]]()

Output ‘s eg

[()]

---

数据范围和约定

设$|s|$为字符串$s$的长度

对于$20\%$的数据，$1 \leq |s| \leq 100$。

对于$50\%$的数据，$1 \leq |s| \leq 10^4$。

对于$100\%$的数据，$1 \leq |s| \leq 10^6$。

---

分析

一道比较套路化的$\text{dp}$模型。

设$f[i]$表示以$s[i]$为结尾的最长匹配子串的长度，则每一个状态可以由其上一位转移而来。

之后考虑如何进行转移。

如果第$i$位为左括号，则不可能构成一个以$s[i]$为结尾的匹配串。此时$f[i] = 0$

如果第$i$位为右括号，则考虑寻找其左边第一个没有匹配的左括号。显然，这之间是不可能有单独的右括号存在的。

也就是说，我们只需要确认当前位置减去前一个位置的最长匹配长度，即$s[i - 1 - f[i - 1]]$是不是左括号即可。是的话，则

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

最后循环一遍，找到最大长度，之后输出子串。

时间复杂度为$O(n)$，足以通过$10^6$的数据。

剩下的见代码注释。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(a))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

char s[10 * M];
int f[10 * M] , ans;    //f[i] 以i为结尾的最长匹配子串长度

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    scanf("%s" , s + 1);    //将字符串统一右移一位以避免负下标
    int len = strlen(s + 1);
    rep(i , 1 , len){
        if(s[i] == '(' || s[i] == '[') continue;    //左括号则跳过
        if(s[i] == ')' || s[i] == ']'){
            if((s[i] == ')' && s[i - 1 - f[i - 1]] == '(') || (s[i] == ']' && s[i - 1 - f[i - 1]] == '[')){
                f[i] = f[i - 1] + 2 + f[i - 2 - f[i - 1]];  
                //右括号的话则等于其上一位长度 + 2 + 之前可以连接的子串长度
                ans = max(ans , f[i]);
            }
        }
    }
    rep(i , 1 , len){
        if(f[i] == ans){
            rep(j , i - ans + 1 , i){   
                printf("%c" , s[j]);
            }
            return 0;
        }
    }

    return 0;
}

---

THE END