2016郑州大学ACM/ICPC训练赛 C 最长匹配子串

Description

定义一个满足括号匹配的字符串为完美串。一个由’(‘,’)’组成的字符串，怎么才能求出
来字符串S中最长的完美串(S的子串)的长度呢？

Input

输入的第一行是一个数字k，代表输入的样例组数（k < 100）。
每组样例是一个字符串只由’(‘,’)’这两个字符组成的字符串s（|s| < 100000)。

Output

输出s中最长的匹配子串的长度。

Sample Input
3
()()
((())
(

Sample Output
4
4
0
HINT

这道题，最好用栈的原理来实现，复杂度为O(n)，也有复杂度为O(n^2)的算法。
先来复杂度高的。
代码C：

#include <stdio.h>
#include <string.h>
char a[100010];
int main()
{
    int t, x, max, i, j, c;

    scanf( "%d", &t);
    getchar();
    while ( t--){
        gets( a);
        x = (int)strlen( a);
        max = i = 0;
        while ( i < x){
            if ( a[i] == '('){
                c = 1;
                for ( j = i + 1; j < x; ++j){
                    if ( a[j] == '(')
                        c++;
                    else
                        c--;
                    if ( c == 0 && j - i + 1 > max)
                        max = j - i + 1;
                    if ( c < 0){
                        i = j;
                        break;
                    }
                }
            }
            i++;
        }
        printf( "%d\n", max);
    }
    return 0;
}

这个方法不是栈的原理，也相对易于理解，但是相比较而言，还是栈高级些，如下：
代码C：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 100000
#define OK 1
#define ERROR 0
#define Max(a, b) ((a > b) ? (a) : (b))
typedef int Status;
typedef int SElemType;
//栈结构
typedef struct
{
    int top;    //用于栈顶指针
    SElemType data[MAXSIZE];
} SqStack;
//Push
Status Push (SqStack *S, SElemType e)
{
    if (S->top == MAXSIZE - 1)  //栈满
    {
        return ERROR;
    }
    S->top++;   //栈顶指针加一
    S->data[S->top] = e;    //将新插入元素
    return OK;
}
//Pop
Status Pop (SqStack *S)
{
    if (S->top == -1)   //栈空
    {
        return ERROR;
    }
    S->top--;
    return OK;
}

int main(int argc, const char * argv[])
{
    int T, ans, tmp, len, last, i;
    char s[MAXSIZE + 5];
    SqStack *S = (SqStack*)malloc(sizeof(SqStack));
    scanf("%d", &T);
    //T组子串
    while (T--)
    {
        S->top = -1;
        scanf("%s", s);
        ans = 0;
        tmp = 0;
        len = (int)strlen(s);
        last = -1;
        //逐字符进行处理
        for (i = 0; i < len; i++)
        {
            if (s[i] == '(')
            {
                Push(S, i);
            }
            else
            {
                if (S->top == -1)
                {
                    last = i;
                    continue;
                }
                Pop(S);
                if (S->top == -1)
                {
                    ans = Max(ans, i - last);
                }
                else
                {
                    ans = Max(i - S->top, ans);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

这里要着重强调的是一定要对定义好的指针进行分配内存，就像实例化类对象时那样，这里要用malloc来进行内存分配，需要调用函数头文件“stdlib.h”。
由于C语言中没有写好的栈函数库，所以都要自己来实现，但是依然是很好的方法，只是这个写法可以进行优化，因为栈的功能很强大，有很多强大的功能我们并不需要用到，所以直接给删去就好了，经过整理可以优化为下代码：
代码C：

#include <stdio.h>
#include <string.h>
#define MAXSIZE 100000
#define Max(a, b) ((a > b) ? (a) : (b))

int main(int argc, const char * argv[])
{
    int T, ans, tmp, len, last, i, top;
    char s[MAXSIZE + 5];
    scanf("%d", &T);
    //T组子串
    while (T--)
    {
        top = -1;
        scanf("%s", s);
        ans = 0;
        tmp = 0;
        len = (int)strlen(s);
        last = -1;
        //逐字符进行处理
        for (i = 0; i < len; i++)
        {
            if (s[i] == '(')
            {
                top++;
            }
            else
            {
                if (top == -1)
                {
                    last = i;
                    continue;
                }
                top--;
                if (top == -1)
                {
                    ans = Max(ans, i - last);
                }
                else
                {
                    ans = Max(i - top, ans);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}