【#138 div 1 A. Bracket Sequence】
【原题】
2 seconds
256 megabytes
standard input
standard output
A bracket sequence is a string, containing only characters "(", ")", "[" and "]".
A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()[]", "([])" are correct (the resulting expressions are: "(1)+[1]", "([1+1]+1)"), and "](" and "[" are not. The empty string is a correct bracket sequence by definition.
A substring s[l... r] (1 ≤ l ≤ r ≤ |s|) of string s = s1s2... s|s| (where |s| is the length of string s) is the string slsl + 1... sr. The empty string is a substring of any string by definition.
You are given a bracket sequence, not necessarily correct. Find its substring which is a correct bracket sequence and contains as many opening square brackets «[» as possible.
The first and the only line contains the bracket sequence as a string, consisting only of characters "(", ")", "[" and "]". It is guaranteed that the string is non-empty and its length doesn't exceed 105 characters.
In the first line print a single integer — the number of brackets «[» in the required bracket sequence. In the second line print the optimal sequence. If there are more than one optimal solutions print any of them.
([])
1
([])
(((
0
【题意】给定长度为N的小、中括号序列，求一个符合括号匹配的子串，使得中括号最多。
【分析】开始想的有点麻烦。感觉是O(N)的扫过去，遇到“)”和“]”注意判无解（如果无解前面全部舍弃掉），然后中括号匹配是这样的——判断这个]和与之匹配的[的“前缀左小括号个数”（显然“(“是会被“)”消掉的）。但是叉点重重。比如[][]，第二组中括号要和第一组发生关系，因此还要用一个类似并查集的东西维护。写起来超级麻烦。
【题解】网上看的思路真是超级清晰。我们用O（N）的方法算出每个点最多能拓展到哪里。
倒着扫，用P[i]表示第i个点向右最多匹配几个字符（包括自己）。
比如当前是i，那么我们知道i+1~i+P[i+1]已经是i+1最大合法状态了。
设next=i+P[i+1]+1,那么判断一下s[i]和s[next]是否匹配。
如果匹配，就能使i~next全部匹配。这是还要判断一下：next+1后面能否继续匹配呢？
于是P[i]=next-i+1+P[next+1],即把next+1的匹配项也加进去。（就想[][]的形态）
注意，不需要加next+1+P[next+1]的P，因为这已经算在P[next+1]上了- -。
【代码】
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
char s[N];int num[N],P[N],ans,i,x,y,L,next;
int main()
{
scanf("%s",s+);L=strlen(s+);
for (i=;i<=L;i++)
num[i]+=num[i-]+(s[i]=='[');
P[L]=;x=;y=;
for (i=L-;i;i--)
{
if (s[i]==')'||s[i]==']') continue;
next=i++P[i+];
if (s[i]=='('&&s[next]==')'||s[i]=='['&&s[next]==']')
P[i]=next-i++P[next+];
}
for (i=;i<=L;i++)
if (num[i+P[i]-]-num[i-]>ans)
ans=num[i+P[i]-]-num[i-],x=i,y=i+P[i]-;
printf("%d\n",ans);
for (i=x;i<=y;i++) printf("%c",s[i]);
return ;
}