字符串匹配

思路：（1）使用普通的字符串匹配方式；（2）遇到括号时单独匹配；（3）每次记录匹配开始的位置；

// c++代码如下
#include <iostream>
using namespace std;
const int sub1 = 'a'-'A',sub2 = 'A'-'a'; // 为了匹配大小写字母
// 因为模式串内不一定只有一对中括号，所以对每一对中括号进行匹配
bool pipeizhongkuohao(char c,string pat,int left,int right) 
// left表示'['下标，rirht表示']'下标
{
    for(int i = left;i<=right;i++) // 这里可以从left+1开始，匹配到right-1结束
    {
        if(c == pat[i] || c == pat[i]+sub1 || c==pat[i]+sub2) return true;
    }
    return false;
}
// 字符串匹配，主串和模式串
int pipei(string str,string pat)
{
    int i = 0,j = 0,k = 0;
    // i表示每次匹配中的主串与匹配位置偏差，j表示模式串偏差，k表示主串匹配开始位置
    while(k<str.size()&&k+i<str.size()&&j<pat.size())
    {
        // 遇到中括号使用中括号匹配
        if(pat[j] == '[')
        {
            int left = j,right = j+1; // 左括号位置
            for(right;pat[right]!=']';right++); // 右括号位置
            bool flag = pipeizhongkuohao(str[k+i],pat,left,right);
            if(flag)
            {
                // 匹配成功，主串偏差值+1，模式串偏差指向右括号下一位置
                i++;j = right+1;
                if(j == pat.size()) return k; // 结束条件
            }
            else{
                // 匹配失败，主串匹配位置+1，偏差均置0，重新匹配
                k++;i=0;j=0;
            }
        }
        else // 字符匹配
        {
            if(str[k+i] == pat[j] || str[k+i] == pat[j]+sub1 || str[k+i] == pat[j] + sub2)
            {
                i++;j++; // 偏差值均+1
                if(j == pat.size())  return k;
            }
            else
            {
                k++;i=0;j=0;
            }
        }
    }
    // 匹配失败
    return -1;
}

int main()
{
    int n;
    while(cin >> n)
    {
        string str[n];
        for(int i = 0;i<n;i++)
            cin >> str[i];
        string pattern;
        cin >> pattern;
        for(int i = 0;i<n;i++)
        {
            if(pipei(str[i],pattern)!=-1) cout << i+1 << ' ' << str[i] << endl;
        }
    }
}