什么是字符串的模式匹配？
是求一个字符串（子串）在另一个字符串（主串）中的位置
BF（暴风算法）
在文本中可能出现匹配的任何地方都检查是否存在。原理很简单，直接看代码就可以懂。
//暴力子字符串查找
public class ViolenceSubStringSearch
{
@SuppressWarnings("unused")
public static int search(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
for(int i = 0; i <= N-M; i++)
{
int j;
for(j = 0; j < M; j++)
{
if(txt.charAt(i + j) != pat.charAt(j));
break;
}
if(j == M)
{
return i; //找到匹配
}
}
return N; //未找到匹配
}
}
KMP
KMP算法的基本思想是当出现不匹配时,就能知晓一部分文本的内容（因为在匹配失败之前他们已经和模式串匹配了）。我们可以利用这些信息避免将指针回退到所有这些已经知晓的字符串前。
KMP的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式串本身。
在KMP子字符串查找算法中，不会回退文本指针i，而是使用一个数组next[] 来记录匹配失败j回退的位置，如何构造next[]数组？
next数组其实是一个有限自动机
判断子串每一位前面存在最大的公共前后缀，来确定i的当前位，需要匹配对应子串j的位置。
KMP 算法简版视频https://www.bilibili.com/video/av49930100?from=search&seid=12985840759395679806
找到最大公共前后缀长度
确定next数组的值
next数组构造过程
next数组确定后，只需要在不匹配的位置上移动，子串的J去做比对，就可以跳过很多不必要的操作。
BM
Boyer−Moore 算法，简称BM 算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下 O(N) 的时间复杂度。在实践中，比 KMP 算法的实际效能高。
BM和KMP这两个算法在最坏情况下均具有线性的查找时间。O(N)。
RK
RabinKarp算法
计算模式字符串的散列函数，然后用相同的散列函数计算文本中所有可能的M个字符的子字符串散列值并寻找匹配。
SUNDAY
KMP 算法并不比最简单的 C 库函数快多少，而 BM 算法虽然通常比 KMP 算法快，但 BM 算法也还不是现有字符串查找算法中最快的算法，最后再介绍一种比 BM 算法更快的查找算法即 Sunday 算法。
它的思想跟 BMBM 算法很相似：
只不过 SundaySunday 算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
否则，其移动位数 = 模式串中最右端的该字符到末尾的距离 + 1。
DFA关键词匹配
之前描述的算法，都是某一个子串在父串中查找匹配的算法，而像或敏感词过滤这种功能，校验多个几百上千个串，检测在父串中是否出现，或替换。则使用DFA算法。
在实现文字过滤的算法中，DFA是唯一比较好的实现算法。DFA即Deterministic Finite Automaton，也就是确定有穷自动机
加入在我们的敏感词库中存在如下几个敏感词：日本人、日本鬼子、日本男人。那么我需要构建成一个什么样的结构呢？
首先：query 日 ---> {本}、query 本 --->{人、鬼子}、query 人 --->{null}、query 鬼 ---> {子}。形如下结构：
image.png
@SuppressWarnings({ "rawtypes", "unchecked" })
private void addSensitiveWordToHashMap(Set<String> keyWordSet) {
sensitiveWordMap = new HashMap(keyWordSet.size()); //初始化敏感词容器，减少扩容操作
String key = null;
Map nowMap = null;
Map<String, String> newWorMap = null;
//迭代keyWordSet
Iterator<String> iterator = keyWordSet.iterator();
while(iterator.hasNext()){
key = iterator.next(); //关键字
nowMap = sensitiveWordMap;
for(int i = 0 ; i < key.length() ; i++){
char keyChar = key.charAt(i); //转换成char型
Object wordMap = nowMap.get(keyChar); //获取
if(wordMap != null){ //如果存在该key，直接赋值
nowMap = (Map) wordMap;
}
else{ //不存在则，则构建一个map，同时将isEnd设置为0，因为他不是最后一个
newWorMap = new HashMap<String,String>();
newWorMap.put("isEnd", "0"); //不是最后一个
nowMap.put(keyChar, newWorMap);
nowMap = newWorMap;
}
if(i == key.length() - 1){
nowMap.put("isEnd", "1"); //最后一个
}
}
}
}
运行得到如下结构的hashMap
{五={星={红={isEnd=0, 旗={isEnd=1}}, isEnd=0}, isEnd=0}, 中={isEnd=0, 国={isEnd=0, 人={isEnd=1}, 男={isEnd=0, 人={isEnd=1}}}}}
检测是否存在违禁词代码：
@SuppressWarnings({ "rawtypes"})
public int CheckSensitiveWord(String txt,int beginIndex,int matchType){
boolean flag = false; //敏感词结束标识位：用于敏感词只有1位的情况
int matchFlag = 0; //匹配标识数默认为0
char word = 0;
Map nowMap = sensitiveWordMap;
for(int i = beginIndex; i < txt.length() ; i++){
word = txt.charAt(i);
nowMap = (Map) nowMap.get(word); //获取指定key
if(nowMap != null){ //存在，则判断是否为最后一个
matchFlag++; //找到相应key，匹配标识+1
if("1".equals(nowMap.get("isEnd"))){ //如果为最后一个匹配规则,结束循环，返回匹配标识数
flag = true; //结束标志位为true
if(SensitivewordFilter.minMatchTYpe == matchType){ //最小规则，直接返回,最大规则还需继续查找
break;
}
}
}
else{ //不存在，直接返回
break;
}
}
if(matchFlag < 2 && !flag){
matchFlag = 0;
}
return matchFlag;
}
网友评论