luogu P1944 最长括号匹配_NOI导刊2009提高

P1944 最长括号匹配_NOI导刊2009提高

2017-08-29

题目描述

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

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

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

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

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

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

【输入样例#1】

([(][()]]()

【输出样例#1】

[()]

【输入样例#2】

())[]

【输出样例#2】

()

【输入样例#3】

([)]

【输出样例#3】

//这里是可爱的空串x

【输入样例#4】

([][])()

【输出样例#4】

([][])()

这个题首先由两个思路x
先说第一个暴力思路(70分)
先找到一个合法括号,用字母A表示。
然后在A的基础上扩展就是(A)|[A]这样的，然后把这些用一个bool数组标记。
这里有一个结论,就是如果一个括号已经有他的另一半，那么他不会被计算两次。
那么扩展完就只是成为A][A或A),两个合法的中间有若干不合法.
然后有一个例子就是[()()]，这是合法的[AA]的情况，所以我们可以在已经求出的数组里扫一下特判。
有这样的扩展。知道没有。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char ch[1000000+999];
bool c[1000000+999];
int ans,k;
bool pd(int one,int two){
    if(ch[one]=='('&&ch[two]==')'){return 1;}
    if(ch[one]=='['&&ch[two]==']'){return 1;}
    return 0;
}
int main(){
    cin>>ch;int len=strlen(ch);
    for(int i=0;i<len;i++){
        if(pd(i,i+1))
        {c[i]=c[i+1]=1;
            int j=2;
            while(1){
                if(i-j+1<0)break;
                if(pd(i-j+1,i+j)){c[i-j+1]=c[i+j]=1,j++;}
                else break;
            }
        }
    }
    for(int i=0;i<len;i++){
        int k,j;k=j=i;
        while(c[k])k--;
        while(c[j])j++;
        if(j>=len&&k<0)break;
        while(!c[k]&&!c[j]){if(pd(k,j))c[k]=c[j]=1,k--,j++;else break;}
}
    for(int i=0;i<len;i++){
        int j=i;
        while(c[j])j++;
        if(j-i>ans)ans=j-i,k=i;
    }
    for(int i=k;i<k+ans;i++)cout<<ch[i];
    return 0;
}

70分暴力

然后（100分）正解其一

用一个栈存之前的'('&'['顺序。如果不合法清空栈，合法弹出栈顶元素继续匹配。

栈中存贮上一个字符在串中位置(数组模拟指针)

还是用bool记录合法的位置。最后找到最长的1就好

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char ch[1000000+999];
bool c[1000000+999];
int a[1000000+999];
int w;
int ans,k;
bool pd(int one,int two){
    if(ch[one]=='('&&ch[two]==')'){return 1;}
    if(ch[one]=='['&&ch[two]==']'){return 1;}
    return 0;
}
int main(){
    scanf("%s",ch);
    int len=strlen(ch);
    for(int i=0;i<len;i++){
        if(ch[i]=='('||ch[i]=='[')w++,a[w]=i;
        else if(pd(a[w],i)&&(w>0))c[a[w]]=c[i]=1,a[w]=-1,w--;
        else for(int j=0;j<=w;j++)a[j]=-1,w=0;
    }
    for(int i=0;i<len;i++){
        int j=i;
        while(c[j])j++;
        if(j-i>ans)ans=j-i,k=i,i=j;
    }
    for(int i=k;i<k+ans;i++)cout<<ch[i];
    return 0;
}

100分

by:s_a_b_e_r

luogu数据好水……

本地样例四卡掉了我的程序，然而luogu上并没有样例四x

思路是用一个栈存字符（编号）

如果栈为空或者不匹配就把字符丢进去

匹配的话就更新下答案

关于处理多个合法字串的问题？

记录一个p数组，用来保存第i个字符向左最长能延伸到哪个字符

每次更新答案时判断一下p[x-1]有没有记录，有的话加长答案

……感觉思路没有错？

因为代码bug所以不丢代码qwq

by:wypx

s:我这是酔了,一开始比赛这题时模拟指针的数组开成char,竟然过了21个点.....233333

w:QWQ依旧调不过去