为了给全球小学员打起信息安全“保护伞”，VIPKID 还建立了一套立体化的安全防御体系，7 \times 247×24 小时持续安全监控与应急响应等多项联动，具备业界最高级别的数据安全保护标准。值得一提的是，VIPKID 也是行业业内唯一通过 ISO 国际信息安全体系认证、公安部信息安全等级保护三级认证的教育企业。
现在安全防御体系就检测到了一个小问题，需要你来帮忙解决其中有关“前驱与后继”的这一部分，让我们一起来守护小学员们的信息安全吧！请看题：
对于两个长度相等的不同的合法括号序列 SS，TT，定义他们之间的大小关系等同于他们字典序的大小关系。
给定一个合法的括号序列 SS，求出 SS 的前驱与后继。
SS 的前驱：所有小于 SS 的串中最大的一个。
SS 的后继：所有大于 SS 的串中最小的一个。
数据保证存在前驱与后继。
一行一个合法括号序列 SS。
第一行一个合法括号序列 pre，表示前驱。
第二行一个合法括号序列 suf，表示后继。
0< | S | \leq 10000000<∣S∣≤1000000
(()())()((()))()
(()())()((())()) (()())()(()(()))
思路：
求前驱：从后往前找第一个使s[i]=‘)‘,s[i+1]=‘(‘的i; i之前的括号不变，交换s[i]和s[i+1]； i之后的括号在保证合法的前提下尽可能填‘)‘
求后继：从后往前找第一个使s[i]=‘(‘,s[i+1]=‘)‘并且在交换s[i],s[i+1]后序列仍合法的i; i之前的括号不变，交换s[i]和s[i+1]； i之后的括号在保证合法的前提下尽可能填‘(‘
AC代码：
#include<bits/stdc++.h> using namespace std; char s[1000005]; int len; char ans[1000005]; void work1(){ int pos; for(int i=len-2;i>=0;i--){ if(s[i]==‘)‘&&s[i+1]==‘(‘){ pos=i; break; } } int cnt=0; for(int i=0;i<pos;i++){ if(s[i]==‘(‘) cnt++; else cnt--; ans[i]=s[i]; } ans[pos]=‘(‘,ans[pos+1]=‘)‘; for(int i=pos+2;i<len;i++){ if(cnt){ ans[i]=‘)‘; cnt--; } else{ ans[i]=‘(‘; cnt++; } } ans[len]=‘\0‘; puts(ans); } void work2(){ int pos,cnt=0; for(int i=0;i<len-1;i++){ if(cnt&&s[i]==‘(‘&&s[i+1]==‘)‘){ pos=i; } if(s[i]==‘(‘) cnt++; else cnt--; } cnt=0; for(int i=0;i<=pos+1;i++){ if(s[i]==‘(‘) cnt++; ans[i]=s[i]; } ans[pos]=‘)‘,ans[pos+1]=‘(‘; cnt=len/2-cnt; for(int i=pos+2;i<len;i++){ if(cnt){ ans[i]=‘(‘; cnt--; } else ans[i]=‘)‘; } ans[len]=‘\0‘; puts(ans); } int main() { scanf("%s",s); len=strlen(s); work1(); work2(); return 0; }
原文：https://www.cnblogs.com/lllxq/p/11046682.html
