关键词：
1.1BF算法
其实就是暴力解法，直接双重循环，干就完事了。虽然算不上什么好方法，但是非常简单。对于所有的暴力算法，我们应该思考如何进行优化，比如BF算法，当我们遇到不匹配字符的时候，只能从头的下一个字符开始匹配。这样其实做了很多无用的重复工作。那么我们可以怎样优化呢？下面介绍两种。二者的思想都是避免无用功的移动。
1.2BM算法
BM算法是从匹配串的后往前匹配。遇到不匹配的字符时，将被匹配串向后移动到匹配字符或者移动到匹配串头。然后再从后往前匹配。
字符串与搜索词头部对齐，从尾部字符开始比较：
这里右移长度有一个规则一：step_bad = pos1 - pos2
step_bad表示向后移动位数；pos1表示坏字符的位置；pos2表示坏字符在搜索词中出现的最右位置（如果不存在就取值为-1）
单是这一条规则并不能保证移动后移长度最合适，我们还需要加一条好后缀规则：step_good = pos1 - pos2
step_good为后移位数；pos1表示好后缀的位置；pos2表示好后缀在搜索词中剩余部分出现的最右位置；
我们发现step_bad 为3 step_good为6，所以我们右移6位。
直到最后得出结果
- 代码
package matchstring;
import java.util.Arrays;
/**
* JavaTest
*
* @author : xgj
* @description : BM算法
* @date : 2020-07-31 22:40
**/
public class BM
public static int pattern(String target , String pattern)
int tLen = target.length();
int pLen = pattern.length();
if (pLen > tLen)
return -1;
int[] badTable = buildBadTable(pattern);
int[] goodTable = buildGoodTable(pattern);
for (int i = pLen - 1, j; i < tLen; )
System.out.println("跳跃位置：" + i);
for (j = pLen - 1; target.charAt(i) == pattern.charAt(j); i--, j--)
if (j == 0)
System.out.println("匹配成功，位置：" + i);
return i;
i += Math.max(goodTable[pLen - j - 1], badTable[target.charAt(i)]);
return -1;
/**
* 字符信息表
*/
public static int[] buildBadTable(String pattern)
final int tableSize = 256;
int[] badTable = new int[tableSize];
int pLen = pattern.length();
Arrays.fill(badTable, pLen);
for (int i = 0; i < pLen - 1; i++)
int k = pattern.charAt(i);
badTable[k] = pLen - 1 - i;
return badTable;
/**
* 匹配偏移表。
*
* @param pattern 模式串
* @return
*/
public static int[] buildGoodTable(String pattern)
int pLen = pattern.length();
int[] goodTable = new int[pLen];
int lastPrefixPosition = pLen;
for (int i = pLen - 1; i >= 0; --i)
if (isPrefix(pattern, i + 1))
lastPrefixPosition = i + 1;
goodTable[pLen - 1 - i] = lastPrefixPosition - i + pLen - 1;
for (int i = 0; i < pLen - 1; ++i)
int glen = suffixLength(pattern, i);
goodTable[glen] = pLen - 1 - i + glen;
return goodTable;
/**
* 前缀匹配
*/
private static boolean isPrefix(String pattern, int p)
int patternLength = pattern.length();
for (int i = p, j = 0; i < patternLength; ++i, ++j)
if (pattern.charAt(i) != pattern.charAt(j))
return false;
return true;
/**
* 后缀匹配
*/
private static int suffixLength(String pattern, int p)
int pLen = pattern.length();
int len = 0;
for (int i = p, j = pLen - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--)
len += 1;
return len;
1.3KMP算法
BM是以被匹配串尾部为基准的话，KMP算法就是以被匹配串头部为基准。相对于而言KMP算法更加接近人的思考方式。
对于暴力算法，在出现不匹配的时候，我们是一位一位的往右移的。但是实际上要是人手工来做的话，会容易发现有时候可以一次移动多位。例如“SSSSSSSSSSSSSA”中查找“SSSSB”。要是人眼比较对于前面的s移动时，会一次性移动到倒数第二位，而不是一位一位的移动。那么在计算机中我们怎么实现聪明的移动呢？“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置”
- 代码
package matchstring;
/**
* JavaTest
*
* @author : xgj
* @description : KMP算法
* @date : 2020-07-31 22:24
**/
public class KMP
/**
*功能描述 : 匹配字符串
*
* @author xgj
* @date 2020/7/31
* @param s
* @param t
* @return boolean
*/
public static boolean matchString(String s, String t)
int[] next = getNext(t);
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
int i = 0, j = 0;
while (i < sArr.length && j < tArr.length)
if (j == -1 || sArr[i] == tArr[j])
i++;
j++;
else
j = next[j];
return j == tArr.length;
/**
*功能描述 : 返回next数组
*
* @author xgj
* @date 2020/7/31
* @param ps
* @return int[]
*/
public static int[] getNext(String ps)
char[] p = ps.toCharArray();
int[] indexArray = new int[p.length];
indexArray[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1)
if (k == -1 || p[j] == p[k])
if (p[++j] == p[++k])
indexArray[j] = indexArray[k];
else
indexArray[j] = k;
else
k = indexArray[k];
return indexArray;
漫画：如何优化“字符串匹配算法”？(代码片段)
漫画：如何优化“字符串匹配算法”？说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了许多巧妙的算法。在上一篇漫画中，我们介绍了BF算法和RK算法，没... 查看详情
算法kmp字符串匹配算法(代码片段)
【原理】（1）next数组原理 （2）特殊情况的处理（巧妙增设哨兵）（3）递推法构造next[]表 【实现代码】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=100;chart[maxn];//textcharp[ 查看详情
字符串匹配算法（bf算法&&kmp算法）(代码片段)
字符串匹配算法暴力匹配（BF）算法KMP算法next数组求next数组的练习next数组的优化（nextval数组）练习暴力匹配（BF）算法BF算法，即暴力(BruteForce)算法，是普通的模式匹配算法，BF算法的思想就是... 查看详情
模式匹配算法(代码片段)
...通过将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一... 查看详情
字符串暴力匹配算法详解(代码片段)
字符串暴力匹配算法详解说明字符串暴力匹配算法是指在一个长字符串中暴力寻找是否包含某一子串所谓暴力匹配，就是不使用任何其他算法，将两个字符串中的字符一一进行比对从长字符串的第一个字符开始，判断是否和子字... 查看详情
kmp算法(代码片段)
基本介绍KMP算法是一种用于字符串匹配的算法，网上关于kmp的介绍很多，也十分复杂，（其实我也没怎么搞懂）。首先我们还是考虑朴素的匹配，暴力枚举匹配起点，遇到不匹配的点，就直接退出，进行下一个起始点开始的一轮... 查看详情
字符串匹配算法知多少？(代码片段)
...法：BM算法坏字符好后缀规则代码实现KMP算法一说到字符串匹配算法，不知道会有多少小伙伴不由自主的想起那个kmp算法呢？想到是很正常的，谁让它那么优秀呢。BF算法不要被事物的表面现象所迷惑，这个算... 查看详情
kmp算法（字符串的匹配）(代码片段)
视频参考 对于正常的字符串模式匹配，主串长度为m，子串为n，时间复杂度会到达O（m*n），而如果用KMP算法，复杂度将会减少线型时间O（m+n）。 设主串为ptr="ababaaababaa";，要比较的子串为a=“aab”； KMP算法用到了next... 查看详情
bf算法（蛮力匹配算法）(代码片段)
...字符和S的开始位置对比，直到S中每一个字符和M中的连续字符串相等，否则不匹配。C#代码-->privatestaticintIndex(stringm,intpos,strings)intm_len=m.Length;ints_len=s.Length;inti=pos-1;int 查看详情
kmp算法详解及其java实现(代码片段)
KMP算法，又称作“看猫片”算法（误），是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经... 查看详情
kmp算法(代码片段)
KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情
kmp算法(代码片段)
KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情
字符串模式匹配中的bf算法与kmp算法(代码片段)
博客园的编辑器太难用了。。。。。。。。。。。BF算法即暴力算法，很简单，随便举个栗子：#include<iostream>#include<cstring>usingnamespacestd;//S[]:要匹配的链//T[]:模式串intBFsearch(intstart,charS[],charT[])intslen=strlen(S);inttlen=strlen(T 查看详情
kmp算法(字符串匹配)(代码片段)
字符串匹配是常见的算法题，就有一个字符串判断里面是否包含另一个字符串。举例来说，有一个字符串"AAAAAABC"（主串），我想知道，里面是否包含另一个字符串"AAAB"（模式串）？... 查看详情
kmp算法(字符串匹配)(代码片段)
字符串匹配是常见的算法题，就有一个字符串判断里面是否包含另一个字符串。举例来说，有一个字符串"AAAAAABC"（主串），我想知道，里面是否包含另一个字符串"AAAB"（模式串）？... 查看详情
字符串匹配算法实现(代码片段)
KMP算法1voidNext(char*src,intn,int*next)23intj,k;4j=0;5k=-1;6next[0]=-1;7while(j<n-1)89if(k==-1||src[j]==src[k])1011++k;++j;12next[j]=k;1314else15k=next[k];16171819intKMP(char*des,intn,char*src 查看详情
python怎么实现模式匹配？(代码片段)
python通过BF算法实现关键词匹配，BF算法，即暴风(BruteForce)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相... 查看详情
数据结构串---bf算法（朴素模式匹配）(代码片段)
...BF算法了解BF算法，即暴风(BruteForce)算法，是普通的模式匹配算法。BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字... 查看详情