In Galgame We Trust
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
As we all know, there are many interesting (H) games in kennethsnow’s computer. But he sets a password for those games. Zplinti1 wants to crack his password and play those games.
Kennethsnow uses only 6 kinds of characters to form his password:
- brackets:
(and) - square brackets:
[and] - curly brackets:
{and}
Kennethsnow’s password must be a correct bracket sequence, and will not be empty.
Zplinti1 found a string written by kennethsnow, and he is sure that kennethsnow’s password is a substring of that, he wonders the maximum possible length of his password, or if his judgment is wrong.
Please note that the original string may also be the password.
Input
The first line of input contains a number T, indicating the number of test cases. (T≤30) For each case, there is a string s, which is the string zplinti1 found. (1≤|s|≤1,000,000, the string will contain those 6 kinds of characters only)
Output
For each case, output Case #i: first. (i is the number of the test case, from 1 to T). If zplinti1’s judgment is wrong (i.e. the answer is 0), output I think H is wrong!, otherwise output a single number, indicating the maximum possible length of kennethsnow’s password.
Sample input and output
| Sample Input | Sample Output |
|---|---|
3 |
Case #1: 6 |
分析：括号匹配，把左括号依次入栈，如果碰到右括号，就与栈顶的元素匹配。用now表示当前的长度，tmp表示连续匹配成功的括号长度。具体看代码。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
using namespace std;
#define INF 100000
typedef long long ll;
const int maxn=;
char s[maxn];
bool match(char s1,char s2){
if(s1=='('&&s2==')') return true;
if(s1=='['&&s2==']') return true;
if(s1=='{'&&s2=='}') return true;
return false;
}
int main()
{
int t,times=;
scanf("%d",&t);
while(t--){
memset(s,,sizeof(s));
scanf("%s",s);
stack<char> p;
int len=strlen(s),lens=,tmp=,now=;
for(int i=;i<len;i++){
if(s[i]=='('||s[i]=='{'||s[i]=='[')
p.push(s[i]);
else{
if(!p.empty()) {
char top=p.top();
if(match(top,s[i])){
p.pop();
tmp+=;
if(p.empty()){ //如果之前的都匹配完了，则更新now
now+=tmp;
lens=max(lens,now);
tmp=;
}
}
else{
while(!p.empty()) p.pop(); //匹配不成功，则把之前的都清空。
lens=max(lens,tmp); //之前的有没匹配成功的，所以不用更新now。
tmp=;
now=;
}
}
else{
now+=tmp;
lens=max(lens,now);
tmp=;
now=;
}
}
}
printf("Case #%d: ",times++);
if(lens!=) printf("%d\n",lens);
else printf("I think H is wrong!\n");
}
return ;
}