大家好，欢迎来到IT知识分享网。

一、字符串匹配算法

字符串匹配这个功能，是非常常见的功能，比如”Hello”里是否包含”el”?

Java里用的是indexOf函数，其底层就是字符串匹配算法。

主要分类如下：

二、BF 算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。

比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串 我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

1、代码实现

public class Bfalth { public static boolean isMatch(String main,String sub){ for(int i=0;i<=(main.length()-sub.length());i++){ // 实际实现是每个字符串做字符比较 ，需要循环子串 if(main.substring(i,i+sub.length()).equals(sub)){ return true; } } return false; } public static void main(String[] args) { System.out.println(isMatch("ccaaac","caaac")); } }

2、时间复杂度

我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。 m:为匹配串长度 n:为主串长度

3、应用

虽然BF算法效率不高但在实际情况下却很常用。因为： 主串不会太长，实现简单