fuzhuo------ Problem 1411 最长配对子串

梦里梦外; 2022-06-15 11:41 91阅读 0赞

** Problem 1411 最长配对子串**

### Accept: 379    Submit: 1470   Time Limit: 1000 mSec    Memory Limit : 32768 KB ###

## ![prodesc.gif][] Problem Description ##

给定由(,),\[,\],\{,\},<,>构成的一个括号字符串，输出它的一个最长子串，该子串有正确的括号配对。

## ![prodesc.gif][] Input ##

本题有多组输入数据，每组数据只有一行括号字符串，其长度不大于10000。

## ![prodesc.gif][] Output ##

对于每组数据，输出该括号字符串的最长配对子串。若答案不唯一，则输出最左边一个；如果答案不存在，则输出“No Solution”。

## ![prodesc.gif][] Sample Input ##

\[()()\]\]\[\]

## ![prodesc.gif][] Sample Output ##

\[()()\]

#include<iostream>
    #include<cstring>
    #include<stack>
    using namespace std;
    struct node
    {
    	int pos;
    	char ch;
    }Node[10010];
    int main()
    {
    	char s[10010];
    	int sign[10010];
    	int i;
        int pos;
    	char ch;
    
    	while(cin>>s)
    	{
    		stack<node> sta;
    		memset(sign,0,sizeof(sign));
    		for(i=0; i<strlen(s); i++)
    		{
    			if(s[i]=='(' || s[i]=='[' || s[i]=='{' || s[i]=='<')
    			{
    				Node[i].ch = s[i];
    				Node[i].pos = i;
    				sta.push(Node[i]);
    			}
    			else
    			{
    				if(!sta.empty())
    				{
    					pos = sta.top().pos;
    					ch = sta.top().ch;
    					if(ch=='('&&s[i]==')' || ch=='['&&s[i]==']' || ch=='{'&&s[i]=='}' || ch=='<'&&s[i]=='>')
    					{
    						sign[i] = 1;
    						sign[pos] = 1;
    						sta.pop();
    					}
    					else
    					{
    					    Node[i].ch = s[i];
    						Node[i].pos = i;
    						sta.push(Node[i]);
    					}
    				}
    			}
    		}
    		int begin,end,max=0;
    		for(i=0; i<strlen(s);)
    		{
    			if(sign[i]==1)
    			{
    				int j=i++;
    				//cout<<"j="<<j<<endl;
    				int temp = 1;
    				while(sign[i] == 1)
    				{
    					temp++;
    					i++;
    				}
    				if(temp > max)
    				{
    					begin = j;
    					end = i-1;
    					max = temp;
    				}
    			}
    			else
                    i++;
    		}
    		if(max != 0)
    		{
    			for(i=begin; i<=end; i++)
    				cout<<s[i];
    		}
    		else
    			cout<<"No Solution";
    		cout<<endl;
    	}
    	return 0;
    }

## ![prodesc.gif][] Source ##

FZUPC 2006

[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif