5
perl
public
python
pearl
private
4
p*
??????
*l
*i*

5
2
2
2

解题思路：

这题开始编写的时候，我很快陷入那种填补式代码的困境，就是不断的调试，发现一个错误然后纠正下代码，又调试，又纠正，最后代码基本上失去管理。。。于是我索性把那些代码全部删除了，整理下思路并在纸上表示出。终于AC了 。。呵呵，思路是最重要的。另外平时练习ACM也应该注意代码的可读性和可复用性。

首先含通配符的串归结为两类：以 * 开头， 以?cc 即不含* 开头的子串开头。对?cc 这一类，我们先找到一个匹配的串，此后以该串后的开始位置匹配后面的串。统一以*开始匹配，我们选出两个*之间（也含*到结尾）的串进行匹配，匹配成功则记录该串的值； 否则就匹配失败。 我们只记录最后的这种串。扫描完表达式串后，如果原串匹配完，或者表达式串的最后一个字符是*则匹配成功，否则在原串的最后位置匹配保存的串。原理： * 后面的串可以是原串后面的任意匹配串。。

如： 原串 str 为： agksdjfDFSgskjfkKKK          表达式 exp 串为： *dj*df*??jfk*

匹配过程： 扫描表达式串 exp 第一位置为 * ，

找到子串 dj　　匹配位置： 　i=4 ,　保存到字符串 lastSubstr = "dj"

继续扫描 exp (从 dj后面开始扫）,　找到子串 df(DF) ,忽略大小写比较 　lastSubstr="df"

……　最后lastSubstr="??jfk",  因为 exp 的最后字符为　＊　，匹配成功；

另：　如果 str = "aksfjkskdfjkslSKD"    exp="aks*jk*Skd"

首先 aks = aks ，exp="*jk*Skd"( 前面的可以不管了)

lastSubstr = jk,   最后 lastSubstr = "Skd".  在 str 的 skdfjkslSKD　匹配，　str 剩余串为

dfjkslSKD, 因为　exp　的最后字符不是 *, 则 lastSubstr　必须与 str 的剩余串尾部匹配这里是 "Skd"="SKD", 匹配成功。

／／／／／／／／　代码　／／／／／／／／／／

#include <iostream>
#include <string>
using namespace std;
const int CSTR_LENGTH = 20;
char gStr[1000][CSTR_LENGTH];

/* 串匹配辅助函数（在 cstr 里查找 str 子串）
 * 参数： i    cstr 的起始匹配下标（匹配成功则返回起始位置）
 *        it   用于返回子串在 cstr 中的最后位置
 *   str  待匹配子串串,可能含有通配符 ?
 *        cstr 原串
 * 返回值： 匹配成功则返回true,同时i,it记录匹配位置, 否则 false
 **/
bool searchMatch(unsigned int& i, unsigned int& it,
        const string& str, const char cstr[]){
    unsigned int si, j;
    for(si=i; cstr[si]!=NULL; si++){
        for(it=si,j=0; j<str.size() && cstr[it]!=NULL &&
            (str[j]=='?' || str[j]==cstr[it]); j++)
            it++;
        if(j>=str.size()){
            i=si;
            return true;
        }
    }
    return false;
}

/* 通配符匹配串函数(长度不限)
 * 参数： str[], 待匹配的C风格字符串（以NULL结尾）
 *       exp[], 含有通配符 ? * 的C风格字符串
 *   isCase : false 忽略大小写匹配， true 区分大小写
 * 返回值: 如果 exp 可以匹配 str 则返回 true ,否则 false
 * 注意：该函数在忽略大小写比较时，会改变原串
**/
bool isMatch(char str[], char exp[], bool isCase){
    /// 是否忽略大小写匹配，是，则全部转为小写形式
    if(!isCase){
        char *p;
        for(p=str; *p!=NULL; p++){
            if(isupper(*p))
                *p = tolower(*p);
        }
        for(p=exp; *p!=NULL; p++)
            if(isupper(*p))
                *p = tolower(*p);
    }
    /// 空串处理，空串或者 “**...*”可以匹配空串
    if(str[0]==NULL){
        int j;
        for(j=0; exp[j] && exp[j]=='*';)
            j++;
        return exp[j]==NULL;
    }else if(exp[0]==NULL)
        return false;
    /// 如果 exp 不以 * 开始，则先匹配开始部分
    unsigned i, j, it, jt;
    for(i=j=0; str[i]!=NULL&&exp[j]!=NULL&&exp[j]!='*'; i++,j++){
        if(exp[j]!='?' && str[i]!=exp[j])
            return false;
    }
    if(str[i]==NULL){
        for(; exp[j] && exp[j]=='*';)
            j++;
        return exp[j]==NULL;
    }else if(exp[j]==NULL)
        return false;
    /// 扫描 以 * 开始的串，进行匹配
    string lastSubstr;
    for(jt=j; exp[jt]!=NULL ; i=it,j=jt){
        for(; exp[j]!=NULL && exp[j]=='*';)
            j++;
        if(exp[j]==NULL)
            break;
        for(jt=j; exp[jt]!=NULL && exp[jt]!='*';)
            jt++;
        string tmp(&exp[j],&exp[jt]);
        if(!searchMatch(i,it,tmp,str))
            return false;
        lastSubstr = tmp;
    }
    /// 最后一个子串（exp中的）处理。
    if(exp[j-1]=='*')
        return true;
    for(i=strlen(str)-lastSubstr.length(),j=0; j<lastSubstr.length(); i++,j++)
        if(lastSubstr[j]!='?' && str[i]!=lastSubstr[j])
            return false;
    return true;
}

int main(){
    int n, m;
    char str[CSTR_LENGTH];
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>gStr[i];
    cin>>m;
    int j, match;
    for(; m--; ){
        cin>>str;
        for(match=j=0; j<n; j++)
            if(isMatch(gStr[j],str,false))
                match++;
        cout<<match<<endl;
    }
    return 0;
}

评论