算法与数据结构—字符串匹配
在字符串str1=”abcabcabdabc” 中寻找str2=”abd” ，那么 str1记为主串，str2即为模式串
BM算法 (Boyer-Moore算法)
理解其起来稍微复杂，但性能号称最高快的算法，比KMP更快 参考：
https://time.geekbang.org/column/article/71187https://www.cnblogs.com/gaochundong/p/boyer_moore_string_matching_algorithm.html
BM 算法包含两部分，分别是坏字符规则和好后缀规则。从右往左匹配
匹配循序：按照模式串从后往前匹配
坏字符规则来计算模式串的滑动位数 主串中的字符串，不在模式串中。则模式串直接移到坏字符串后面。
当遇到坏字符时，要计算往后移动的位数 si-xi 坏字符规则避免在模式串中遍历 在模式串中顺序遍历查找，比较低效，会影响性能，将模式串中的每个字符及其下标都存到散列表中
坏模式，在主串中a，与模式匹配，如果不匹配，看是否在模式串中，在，则后移模式串使得模式串中最后面的a与主串对齐；不在模式串中，则直接后移模式串到a后面一位、
好后缀规则 模式串和主串已经匹配好的字符串部分{u}
在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u}，滑动到子串{u}与主串中{u}对齐的位置
怎么提升好后缀匹配效率 不是主串与模式串的一一匹配，而是实现计算出 “坏字符规则之向后位移表” 和 “好后缀规则之向后位移表”。只要给出坏字符的位置即可获取对应的后移距离
后缀子串：cabcab的后缀子串：b, ab,cab, bcab, abcab 前缀子串：cabcab的前缀子串有：c, ca, cab, cabc, cabca
BM算法小结 Boyer–Moore 算法的精妙之处在于，其通过两种启示规则来计算后移位数，且其计算过程只与模式 P 有关，而与文本 T 无关。因此，在对模式 P 进行预处理时，可预先生成 “坏字符规则之向后位移表” 和 “好后缀规则之向后位移表”，在具体匹配时仅需查表比较两者中最大的位移即可。 好后缀规则还可以独立于坏字符规则使用，坏字符规则实现起来有点耗内存。为了节省内存，可以只用好后缀规则，当然性能也会略有下降。
here is an simple example example
//BM 算法
public class BM {
private static final int SIZE = 256;
/**
* 构建模式串哈希表
* 根据asciiTable实现O(1)时间判断字符是否在模式串中
* @param preg 模式串
* @param pregLength 模式串长度
* @param asciiTable 哈希表 key为字符ASCII码值，value为字符在模式串中最后出现的位置
*/
public void generateBC(char[] preg, int pregLength, int[] asciiTable) {
for (int i = 0; i < SIZE; i++) {
asciiTable[i] = -1;
}
for (int i = 0; i < pregLength; i++) {
int ascii = (int)preg[i]; //计算字符ascii码值
asciiTable[ascii] = i;
}
}
/**
*
* @param mainStr 主字符串
* @param mainStrLength 主串长度
* @param preg 模式串
* @param pregLength 模式串长度
* @return
*/
public int bm(char[] mainStr, int mainStrLength, char[] preg, int pregLength) {
int[] bc = new int[SIZE]; //记录模式串中每个字符串最后出现的位置
generateBC(preg, pregLength, bc); //构建模式串hash表，用于快速判断是否在模式串中出现
int[] suffix = new int[pregLength];
boolean[] prefix = new boolean[pregLength];
generateGS(preg, pregLength, suffix, prefix); //根据模式串，计算公共后缀以及公共后缀是否也也是模式子前缀
int i = 0; //模式串第一个字符与主串对齐的位置
while (i <= mainStrLength - pregLength) {
int j; //模式串中的位置
for (j = pregLength - 1; j >= 0; j--) {//从模式串最后一位往前匹配
if (mainStr[i+j] != preg[j]) break;
}
if (j < 0)
return i; //匹配成功
//模式串往后移动, 使坏字符串与模式串中最后一个与之相同的坏字符串对齐，不存在不存在就移动j-(-1)=pregLength位
int badVar = j - bc[(int)mainStr[i+j]]; //坏字符移动 的距离
int goodVar = 0; //好规则移动的距离
if (j < pregLength - 1) {
goodVar = moveByGS(j, pregLength, suffix, prefix);
}
i = i + Math.max(badVar, goodVar); //向后移动模式串
}
return -1;
}
/**
*
* @param j 坏字符串位置
* @param pregLength
* @param suffix
* @param prefix
* @return
*/
private int moveByGS(int j, int pregLength, int[] suffix, boolean[] prefix) {
int k = pregLength - 1 - j; // 好后缀长度
if (suffix[k] != -1) //好后缀出现在模式串中
return j - suffix[k] + 1; // 好后缀当前位置j - 好后缀在模式串中最右出现的位置
//遍历好后缀的子串
for (int r = j + 2; r < pregLength - 1; r++) {
if (prefix[pregLength-r] == true) {
return r;
}
}
return pregLength;
}
/**
* 这个方法与主串无关，是在搜索前，事先就可以计算好的
* 根据模式串，计算公共后缀以及公共后缀是否也也是模式子前缀
* @param preg
* @param pregLength
* @param suffix
* @param prefix
*/
public void generateGS(char[] preg, int pregLength, int[] suffix, boolean[] prefix) {
for (int i = 0; i < pregLength; i++) {//初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < pregLength - 1; i++) { //列举出所有好后缀的情况
int j = i;
int k = 0; //公共后缀子串长度
//列举出在模式串中再次出现的后缀串
while (j >= 0 && preg[j] == preg[pregLength-1-k]) {
j--;
k++;
suffix[k] = j + 1; //先列出所有的 后缀子串数组suffix[长度] = 首次出现位置
}
if (j == -1)
prefix[k] = true; //表示 公共子串后缀 也是模式前缀
}
}
/**
*
* bm算法(只有坏字符规则启示)
* @param mainStr 主字符串
* @param mainStrLength 主串长度
* @param preg 模式串
* @param pregLength 模式串长度
* @return
*/
public int bmBad(char[] mainStr, int mainStrLength, char[] preg, int pregLength) {
int[] bc = new int[SIZE]; //记录模式串中每个字符串最后出现的位置
generateBC(preg, pregLength, bc);
int i = 0; //模式串第一个字符与主串对齐的位置
while (i <= mainStrLength - pregLength) {
int j; //模式串中的位置
for (j = pregLength - 1; j >= 0; j--) {//从模式串最后一位往前匹配
if (mainStr[i+j] != preg[j]) break;
}
if (j < 0)
return i; //匹配成功
//模式串往后移动, 使坏字符串与模式串中最后一个与之相同的坏字符串对齐，不存在不存在就移动j-(-1)=pregLength位
i = i + (j - bc[(int)mainStr[i+j]]);
}
return -1;
}
}
//bm运行测试
public static void test2() {
BM bm = new BM();
String str1 = "abcabcabdabc";
String str2 = "abd";
char[] mainStr = str1.toCharArray();
char[] preg = str2.toCharArray();
int ret;
ret = bm.bm(mainStr, mainStr.length, preg, preg.length);
System.out.println(ret);
}
BM 算法。复杂、难懂，但匹配的效率却很高，在实际应用中，特别是一些文本编辑器，应用比较多。 BM 算法的时间复杂度分析起来非常复杂。时间复杂度为O(n)。
RK算法(Rabin-Karp 算法)
主串长n，模式串场m.
把主串分解成n-m+1个子串 n-m+1 个长度为 m 的子串，只需要暴力地对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串。
怎么提高n-m+1子串与模式串的匹配效率？ 求出子串和模式串的哈希值，比较他们的哈希值。数字肯定字符串比较高效很多，只要哈希算法高效即可。 哈希算法： 假设要匹配的字符串的字符集中只包含 K 个字符，可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。如，这个 K 进制数转化成十进制数，作为子串的哈希值。只需要把进位从 10 改成 26 就可以。即a代表0，z代表25
123 = 1 * 10^2 + 2 * 10^1 + 3 cba = c * 26^2 + b * 26^1 + a = 2 * 26^2 + 1 * 26^1 + 0 = 1353
时间复杂度： O(n) 模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，共需要比较 n-m+1 个子串的哈希值。当然如果哈希冲突较多，会导致RK算法效率下降。
BF算法(Brute Force 暴力匹配算法)
最为简单，但是用的挺多，且不易出错。
- 因为实际中可能匹配的字符串不长。这个算法很简单，且不易出错。所以也是常用的
主串长n，模式串场m 依次遍历主串，将主串中的字符挨个与模式串的比较，时间复杂度最坏 O(n*m)
KMP算法
模式串P， 主串T， i为主串中游标，j为模式串中游标。
一直j为模式串中坏字符的位置，则模式串中最前面的k个字符和j之前的最后k个字符有关系：k为匹配的长度，也可能不存在
P[0 ~ k-1] == P[j-k ~ j-1]
当T[i] != P[j]时（出现坏字符时），有T[i-j ~ i-1] == P[0 ~ j-1] （坏字符之前的字符还是可以匹配的），由P[0 ~ k-1]= P[j-k ~ j-1]可以的得到 T[i-k ~ i-1] = P[0 ~ k-1]， 即主串中坏字符前面的子串与模式串中前缀子串出现匹配时可移动模式串使这部分对齐。
数组next next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置。 i为主串中游标，j为模式串中游标， 当出现坏字符时，j很可能需要往左移，重新比较。j最多也只能左移到0，到0，就只能右移i了。next[0] = -1;
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。(即
当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next值)
next 数组各值的含义
失配时，next[j]即为下一步j的位置
代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符；若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
最大前缀后缀公共元素长度
复杂度分析 假设主串长n， 模式串长m 只需要一个next[m]的数组放next,故空间复杂度O(m) 求next的 时间复杂度为O(m)，主串遍历为O(n); 索引时间复杂度为O(m+n) 主串i始终是一位一位的往后移动，模式串的j才能根据next数组进行多步移动（这个规则注定没有bm算法效率高）。
/**
* 计算失配函数，用于获取j失配时，下一个位置; next[j] 就是最大前缀后缀公共子串长度的数组
* @param p
* @return
*/
public int[] getNext(char[] p) {
int[] next = new int[p.length];
int k = -1;
int j = 0;
next[0] = -1;
while (j < p.length - 1) {
//这里相当于p[0~j]是主串，p[0~k]是模式串
if (k == -1 || p[j] == p[k]) {//p[j] == p[k]表示找到了公共前后缀子串,加到next中，继续往后
j++;
k++;
next[j] = k;
} else {
//p[j] != p[k]时，就不能找到比k更长的公共子串了，k需要重新开始，但是next[k]更快的移动。
//还是利用kmp，p[0~j]是主串，p[0~k]是模式串，k类似之前的j，还是找最大前缀后缀公共子串
k = next[k];
}
}
return next;
}
public int kmpSearch(String mainStr, String preg) {
int i = 0;//主串搜索
int j = 0;//模式串搜索
char[] s = mainStr.toCharArray();
char[] p = preg.toCharArray();
int[] next = getNext(p);
while (i < s.length && j < p.length) {
if (j == -1 || s[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j >= p.length)
return i - j;
return -1;
}
https://blog.csdn.net/v_july_v/article/details/7041827
https://www.cnblogs.com/yjiyjige/p/3263858.html
https://time.geekbang.org/column/article/71845
Tire树（字典树）
Trie 树，也叫“字典树”，一种解决字符串快速匹配问题的数据结构。 Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起, 作为父节点。
浪费内存？
- 用数组存储子节点的地址，建立哈希表实现O(1)访问子节点；但是可能造成内存的利用率太低。典型的空间换时间。
- 有序数组存储， 牺牲一定的访问效率，使用有序数组，通过二分法查找子节点。但是维护有点费时。
字符集太大，那存储空间可能就会浪费很多。 字符串的前缀重合比较多，不然空间消耗会变大很多。 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打折的 在一组字符串中查找字符串的问题，更倾向于用散列表或者红黑树。这两种数据结构，直接利用编程语言中提供的现成类库就行了。
Trie 树比较适合的是查找前缀匹配的字符串，比如搜索引擎提供的前缀关键词推荐，输入补全功能
//字典数
public class Trie {
private TrieNode root = new TrieNode('/');
public void insert(String text) {
char[] cs = text.toCharArray();
TrieNode p = root;
//hello
for (int i = 0; i < cs.length; i++) {
int index = cs[i] - 'a';
if (p.child[index] == null) {
TrieNode newNode = new TrieNode(cs[i]);
p.child[index] = newNode;
}
p = p.child[index];
}
p.isEnd = true;
}
public boolean find(String text) {
TrieNode p = root;
char[] cs = text.toCharArray();
for (int i = 0; i < cs.length; i++) {
int index = cs[i] - 'a';
if (p.child[index] != null) {
p = p.child[index];
} else {
return false;
}
}
return true;
}
//字典树节点
public class TrieNode {
public char data;
public TrieNode[] child = new TrieNode[26]; //用于存储子节点
public boolean isEnd = false;
public TrieNode(char data) {
this.data = data;
}
}
}
AC自动机
单模式串匹配算法 一个模式串和一个主串进行匹配 BF 算法、RK 算法、BM 算法、KMP 算法都是单模式串匹配算法
多模式串匹配算法 多个模式串和一个主串进行匹配 Trie 树是多模式串匹配算法
如果实现一个高性能敏感词过滤系统 维护一个大的敏感词字典表（模式串），即对敏感词建立一棵字典树（trie树），把对用户输入做主串，依次到字典树中查找，中途遇到不匹配的，就把主串中的i往后移一位，重新到tire树种匹配。
经典的多模式串匹配算法：AC 自动机 AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的next 数组是构建在树上罢了。 即每个节点都有一个失败指针，当出现匹配失败时，找到最长后缀与其他模式串的前缀的最大公共子串，
在AC自动机中，有类似next数组的东西就是fail指针，当发现失配的字符失配的时候，跳转到fail指针指向的位置，
其实，如果我们把树中相同深度的节点放到同一层，那么某个节点的失败指针当发现失配的字符失配的时候，跳转到fail指针指向的位置，只有可能出现在它所在层的上一层。 失败指针的构建过程，是一个按层遍历树的过程。
import java.util.LinkedList;
import java.util.Queue;
//AC自动机
public class AC {
private AcNode root = new AcNode('/');
public void insert(String text) {
char[] cs = text.toCharArray();
AcNode p = root;
//hello
for (int i = 0; i < cs.length; i++) {
int index = cs[i] - 'a';
if (p.children[index] == null) {
AcNode newNode = new AcNode(cs[i]);
newNode.length = i + 1;
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEnd = true;
}
//建立失败指针数组，整体实在做层遍历
public void buildFailurePointer() {
Queue<AcNode> queue = new LinkedList<>();
root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcNode p = queue.remove();
for (int i = 0; i < 26; ++i) {
AcNode pc = p.children[i];
if (pc == null) continue;
if (p == root) {
pc.fail = root;
} else {
AcNode q = p.fail;
while (q != null) {
//获取失败指向的节点的对应子节点是否也存在,存在则当前字节点失败指向它
AcNode qc = q.children[pc.data - 'a'];
if (qc != null) {
pc.fail = qc;
break;
}
//如果获取失败指向的节点q的对应子节点不存在，则让q的失败指针继续重复前面的操作。直到为null
q = q.fail;
}
if (q == null) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
public void match(char[] text) {
int n = text.length;
AcNode p = root;
for (int i = 0; i < n; ++i) {
int idx = text[i] - 'a';
while (p.children[idx] == null && p != root) {
p = p.fail;
}
p = p.children[idx];
if (p == null) {
// 如果没有匹配的，从 root 开始重新匹配
p = root;
continue;
}
AcNode tmp = p;
while (tmp != root) {
if (tmp.isEnd == true) {//匹配到合适的模式串时(敏感词)
int pos = i-tmp.length+1;
System.out.println(" 匹配起始下标 " + pos + "; 长度 " + tmp.length);
}
tmp = tmp.fail;
}
}
}
public class AcNode {
public char data;
public AcNode[] children = new AcNode[26]; //用于存储子节点
public boolean isEnd = false;
public int length = -1;
public AcNode fail = null; //失败指针，用于指定匹配失败时，下一个去的位置
public AcNode(char data) {
this.data = data;
}
}
}
如何量化两个字符串的相似度？
编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；