微软面试题解析：实现一个挺高级的字符匹配算法

微软面试题解析：实现一个挺高级的字符匹配算法2014-12-25题目：

给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3这些都要找出来

其实就是类似一些和谐系统。

分析：

自然匹配就是对待匹配的每个字符挨个匹配
设你的待匹配字串长度位n,模式字符串长度位m.
对于待匹配字符串中的任意一个字符最坏情况下要匹配m次，也就是说这个字符不在模式字符串中。
所以最坏情况下总共是m*n此匹配，时间复杂度就是O（m*n）

可以简单的实现下：

#include<iostream>#include<string.h>using namespace std;void search_str（char* src, char* dst）{for（int i=0; i < strlen（src）; i++）{int j = 0;for（j = 0; j < strlen（dst）; j++）if（src[i] == dst[j]）break;if（j < strlen（dst））cout << src[i];elsecout << "*";}}int main（）{char s[] = "12436781563";char d[] = "123";search_str（s, d）;return 0;}

输出结果如下：

12*3***1**3

作者：csdn博客 hhh3h