假设模式串中包含"*"和"?", 判断给出的串是否和模式串匹配。
这个题是个表面容易的题,实际不不好做,没做过的话应该至少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);
- }
阅读(4328) | 评论(1) | 转发(1) |