含有通配符的字符串模式匹配

假设模式串中包含"*"和"?", 判断给出的串是否和模式串匹配。

 

这个题是个表面容易的题，实际不不好做，没做过的话应该至少20分钟。

不可以简单的正向循环，否则类与abb与a*b的匹配就会出问题。

提供递归算法代码（codepad.org已验证）

非递归算法待补

 

算法描述：

定义如果匹配返回0，如果不匹配返回1.

用i表示当前处理的串下标，j表示当前处理的模式串的下标.

那么， 对于f(i,j)有

          f(i,j) = f(i-1,j-1) (src[i] == pattern[j] || pattern[j] == '?')

                   f(i-1,j)&f(i-1,j-1) (patter[j] == '*')

 

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

int test(const char* src, const char* pattern, int si, int pi){
    if(src == NULL || pattern == NULL) return -1;
    if(si<0&&pi<0) return 0;
    if(si<0||pi<0) return 1;

    if(pattern[pi] == '*'){
        int movep = test(src, pattern, si-1, pi-1);
        int nmovep = test(src, pattern, si-1,pi);
        return movep&nmovep;
    }
    if(src[si] == pattern[pi] || pattern[pi] == '?'){
        return test(src,pattern,si-1,pi-1);
    }
    return 1;
}
int main(){
    char* src = "testthefunction";
    char* pattern = "t*t?e*ion";
    int ret = test(src, pattern, strlen(src)-1, strlen(pattern)-1);
    printf("result = %d \n", ret);
}