前言：一直都这样认为“正则表达式是一个很有用的技能”，从一开始的磕磕绊绊的使用和摸索，到后来可以得心应手，这个过程离不来平时的不断学习和思考🤔。但最近在想正则表达式是如何实现的（即算法），故这几天一直在找相关的博客来学习，慢慢的也大概了解了正则表达式的实现原理。
一：DFA算法
背景>>一个解决查找一些关键词的算法
例如：我要查找一篇文章中，“电影”，“电视”，“电视节目”，“春天”........这个词语出现的次数。
*DFA查找思路
步骤1：遍历该文章中每个字符，并且查看是否含有字符“电”和“春”字符。如果不含有则直接返回false即不含关键字，如果含有（如电）进行步骤2
步骤2：继续查找下一个字符，判断该字符是否是“影”，“视”。如果下一个字符是“影”，这则把电影返回到一个集合中，继续步骤1，直到结束.
*如何通过算法实现DFA算法
1.首先要构建一个关键字的集合（map）
这个map的特点是，至少有两个值
值1： 记录 关键字（电）=值（又是一个map） //如果是多个值则是关键字是“视”，“影”
值2：记录 状态 = 状态值（是否可以结束）
例如：{电={影={isEnd=1}, 视={节={isEnd=1}, isEnd=0}, isEnd=0}}
Java：实现
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"); //最后一个 } } } System.out.println(sensitiveWordMap.toString()); }
2.遍历文章的每个字符，
步骤1 ：查看该字符在集合中是否存在，如果不存在，则继续查询下一个继续判断步骤1直至结束，如果存在进行步骤2
步骤2：获取该关键字的值的集合，并获取该集合的isEnd属性值，如果为1则表示可以返回并且找到关键字。如果为0则执行步骤3，
步骤3: 获取该关键字的值的集合，并做当前集合。查找下一个字符，并判断该集合中是否存在，如果不存在则返回（表示该关键字查找失败），如果存在循环步骤2
Java实现
@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) { // 长度必须大于等于1，为词
matchFlag = 0;
}
return matchFlag;
}
编目地址：git:SensitivewordFilter.java和SensitiveWordInit
运行实例：
public static void main(String[] args) { SensitivewordFilter filter = new SensitivewordFilter(); System.out.println("敏感词的数量：" + filter.sensitiveWordMap.size()); String string = "太多的电视节目"; System.out.println("待检测语句字数：" + string.length()); long beginTime = System.currentTimeMillis(); Set<String> set = filter.getSensitiveWord(string, 2); long endTime = System.currentTimeMillis(); System.out.println("语句中包含敏感词的个数为：" + set.size() + "。包含：" + set); System.out.println("总共消耗时间为：" + (endTime - beginTime)); } {电={影={isEnd=1}, 视={节={isEnd=1}, isEnd=0}, isEnd=0}, 春={isEnd=1}} 敏感词的数量：2 待检测语句字数：7 语句中包含敏感词的个数为：1。包含：[电视节] 总共消耗时间为：0
