下面几篇文章记录字符串匹配算法。Brute-Force算法简称BF算法，中文名叫简单匹配算法。正...
下面几篇文章记录字符串匹配算法。
Brute-Force算法简称BF算法，中文名叫简单匹配算法。正如其名，简单粗暴，按部就班地遍历所有字符，算法简单，效率低下，不被看好。
但也正因为不常用，反而容易生疏了，因此以此文熟悉一下这一简单的算法。
算法思想：对于源串source和模式串pattern，从source的第1个字符开始和pattern匹配；如果遇到不相同字符，则从source的第2个字符开始，重新和pattern匹配；如此循环，直至在source中遇到可以完全匹配pattern的序列，或者source遍历到尾部。
效率分析：假设source的长度为n，pattern的长度为m，不难看出，最坏情况下，对于source的每个字符，都要遍历一遍pattern，因此时间复杂度为O(n*m)。
代码实现：下面是BF算法的C语言实现
int BruteForce(char *source, char *pattern){ int i, j; int m, n; if (source == NULL || pattern == NULL) { return -1; } m = strlen(pattern); n = strlen(source); if (m == 0) { return -1; } for (i = 0; i <= n - m; ++i) { j = 0; while (j < m && source[i + j] == pattern[j]) { ++j; } if (j == m) { return i; } } return -1;}版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：CentOS6上安装dnsmasq-full+ipset+SS 下一篇：取数字问题
