CF 제목 모음 PART 1 #138 div 1 A

【#138 div 1 A. Bracket Sequence】
[원제]
A. Bracket Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
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.
Input
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.
Output
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.
Sample test(s)
input

([])

output

1
([])

input

(((

output

0

[제의] 길이가 N인 작고 중괄호 서열을 정하고 괄호와 일치하는 자열을 구하여 중괄호가 가장 많도록 한다.
[분석] 좀 귀찮게 생각하기 시작했어요.O(N)가 지나가는 것 같아서')'와']'를 만나면 무해(무해 앞에서 모두 버릴 경우)를 주의하고 중괄호가 일치하는 것은 이렇다. 이것과 일치하는 [접두사 왼쪽 소괄호 개수'(분명히'은')'에서 사라진다)를 판단한다. 그러나 포크가 무겁다. 예를 들어 [][][]를 보면 두 번째 조의 중괄호는 첫 번째 조와 관계가 있기 때문에 비슷한 것을 찾아서 유지해야 한다.쓰기가 너무 귀찮아요.
인터넷에서 보는 사고방식이 정말 뚜렷하다.우리는 O(N)의 방법으로 각 점이 가장 많이 넓어질 수 있는 곳을 계산해 낸다.
거꾸로 쓸고 P[i]로 i번째 점이 오른쪽으로 최대 몇 글자(자신 포함) 일치하는 것을 나타낸다.
예를 들어 현재 i라면 i+1~i+P[i+1]는 이미 i+1의 최대 합법적인 상태임을 알 수 있습니다.
nxt=i+P[i+1]+1을 설정하면 s[i]와 s[nxt]가 일치하는지 판단합니다.
일치하면 i~next가 모두 일치합니다.이것은 또한 판단해야 한다:next+1 뒤에 계속 일치할 수 있습니까?
그래서 P[i]=next-i+1+P[next+1], 즉next+1의 일치항도 추가합니다.([][]]의 형태만 생각하면)
이것은 이미 P[next+1]에 포함되었기 때문에 Next+1+P[next+1]의 P를 추가할 필요가 없습니다.
【코드】

#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+1);L=strlen(s+1);
  for (i=1;i<=L;i++)
    num[i]+=num[i-1]+(s[i]=='[');
  P[L]=0;x=1;y=0;
  for (i=L-1;i;i--)
  {
    if (s[i]==')'||s[i]==']') continue;
    next=i+1+P[i+1];
    if (s[i]=='('&&s[next]==')'||s[i]=='['&&s[next]==']')
      P[i]=next-i+1+P[next+1];
  }
  for (i=1;i<=L;i++)
    if (num[i+P[i]-1]-num[i-1]>ans)
      ans=num[i+P[i]-1]-num[i-1],x=i,y=i+P[i]-1;
  printf("%d
",ans);
  for (i=x;i<=y;i++) printf("%c",s[i]);
  return 0;
}