Pattern Matching(正则表达式匹配)

Pattern Matching

---

Time Limit:1s	Memory limit:32M
Accepted Submit:3	Total Submit:22

---

Background

A regular expression is a string which contains some normal characters and some meta characters. The meta characters include

.	means any character
[c1-c2]	means any character between c1 and c2 (c1 and c2 are two characters)
[^c1-c2]	means any character not between c1 and c2 (c1 and c2 are two characters)
*	means the character before it can occur any times
+	means the character before it can occur any times but at least one times
\	means any character follow should be treated as normal character

You are to write a program to find the leftmost substring of a given string, so that the substring can match a given regular expression. If there are many substrings of the given string can match the regular expression, and the left positions of these substrings are same, we prefer the longest one.

Input

Every two lines of the input is a pattern-matching problem. The first line is a regular expression, and the second line is the string to be matched. Any line will be no more than 80 character. A line with only an " end " will terminate the input.

Output

For each matching problem, you should give an answer in one line. This line contains the string to be matched, but the leftmost substring that can match the regular expression should be bracketed. If no substring matches the regular expression, print the input string.

Sample Input

.* 
asdf 
f.*d. 
sefdfsde 
[0-9]+ 
asd345dsf 
[^\*-\*] 
**asdf**fasd 
b[a-z]*r[s-u]* 
abcdefghijklmnopqrstuvwxyz  
[T-F] 
dfkgjf 
end 

Sample Output

(asdf) 
se(fdfsde) 
asd(345)dsf 
**(a)sdf**fasd 
a(bcdefghijklmnopqrstu)vwxyz 
dfkgjf 

Hints

1. There may be some case like this : 1****,2+++++
2. There may be lines having more than 80 characters(but be sure less than 200)
3. You must check the end of file as the end of the datas. There will be no line with a single "end".

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define Range 0
#define NRange 1
#define Dot 2
#define Normal 3

struct Match_block
{
    char begin;
    char end;
    int flag;
};

char *begin, *end;
int flag;
char g_str[500], g_matched[500];

int pattern_match(char *str, char *matched)
{
    char temp;
    int i, r0, r1;
    struct Match_block block;

    if (*str == '\0' || *str == '\n')
    {
        if (begin == matched)
            return 0;
        if (end < matched)
            end = matched;
        flag = 1;
        return 0;
    }

    switch(*str)
    {
    case '\\':
        ++str;
        block.begin = *str;
        block.flag = Normal;
        break;
    case '.':
        block.flag = Dot;
        break;
    case '[':
        ++str;
        if (*str == '^')
        {
            ++str;
            block.flag = NRange;
        }
        else
            block.flag = Range;
        if (*str == '\\')
            ++str;
        block.begin = *str;
        str += 2;
        if (*str == '\\')
            ++str;
        block.end = *str;
        if (block.begin > block.end)
        {
            temp = block.begin;
            block.begin = block.end;
            block.end = temp;
        }
        ++str;
        break;
    default:
        block.begin = *str;
        block.flag = Normal;
        break;
    }
    ++str;

    if (*str != '*' && *str != '+')
        r0 = r1 = 1;
    else
    {
        r1 = 100000000;
        r0 = 1;
        while (*str == '*' || *str == '+')
        {
            if (*str == '*' && str[-1] != '+')
                r0 = r0 & 0;
            else
                r0 = r0 & 1;
            ++str;
        }
    }

    for (i = r0; i <= r1; ++i, ++matched)
    {
        if (i == 0)
            pattern_match(str, matched);
        if (*matched == '\0' || *matched == '\n')
            return 0;
        switch(block.flag)
        {
        case Range:
            if (*matched >= block.begin && *matched <= block.end)
                pattern_match(str, matched + 1);
            else
                return 0;
            break;
        case NRange:
            if (!(*matched >= block.begin && *matched <= block.end))
                pattern_match(str, matched + 1);
            else
                return 0;
            break;
        case Dot:
            pattern_match(str, matched + 1);
            break;
        case Normal:
            if (*matched == block.begin)
                pattern_match(str, matched + 1);
            else
                return 0;
            break;
        }
    }

    return 0;
}

int main()
{
    char *p = NULL;
    
    while(gets(g_str))
    {
        gets(g_matched);
        if (strcmp(g_str, "end") == 0)
            break;

        if (g_str[0] == '\0' || g_str[0] == '\n')
        {
            printf("%s\n", g_matched);
            continue;
        }

        flag = 0;

        p = g_str;
        begin = g_matched;
        end = begin - 1;
        while (*begin != '\0' && *begin != '\n')
        {
            pattern_match(p, begin);
            if (flag)
                break;
            begin++;
        }

        for (p = g_matched; *p; ++p)
        {
            if (p == begin)
                printf("(");

            printf("%c", *p);

            if (p == end - 1)
                printf(")");
        }
        printf("\n");
    }

    return 0;
}