字符串匹配——Brute-Force 简单匹配算法
2024-10-06 10:15:16
下面几篇文章记录字符串匹配算法。
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;
}
最新文章
- Openvpn 撤销签署的证书(删除用户)
- iOS开发常见BUG和一些小技巧(ps:耐心看完,很实用)
- JSON拾遗
- 封装好的socket,拿去用
- phpcms_v9 多图字段 内容页,首页,分页自定义字段调用
- win32手动创建windows窗口的,小记
- 【转】iOS超全开源框架、项目和学习资料汇总
- C#中String.Empty,“”,NULL的区别
- 关于fork函数中的内存复制和共享
- PS 颜色表大全-颜色中文名(1)
- 【JAVA】导出jar包时,Class files on classpath not found
- ASP.NET中ListBox控件的使用
- NEWS-包名-baseTest-类名-ConfigManager
- Java 将容器 Map中的内容保存到数组
- C++STL模板库序列容器之vector
- JAVA工具类-StrUtils
- zookeeper启动时报Cannot open channel to X at election address Error contacting service. It is probably not running.
- [Proposal][app]觅食去
- 【随记】Q号解除限制一波三折
- Homestead在windows7 下的搭建
热门文章
- Javascript 运动中Offset的bug——逐行分析代码,让你轻松了解运动的原理
- linux---finger命令
- QT里嵌入Python
- android:TextAppearance.Material.Widget.Button.Inverse问题
- Learn X in Y minutes(python一页纸代码)
- POJ 3740 DLX
- Centos6.5 Qt4开发 Cannot find -lGL QApplication not file or dir
- HTML字符实体(Character Entities),转义字符串(Escape Sequence)【转】
- 使用Vitamio打造自己的Android万能播放器(1)——准备
- LeetCode: Surrounded Regions [130]