字符串匹配算法

女爷i 2023-06-23 02:56 234阅读 0赞

主要算法：BF RK BM KMP Sunday算法

BF ：Brute Force，暴力匹配算法  
字符串A中查找字符串B  
主串：A，长度n  
模式串：B，长度m  
检查起始位置分别是0,1,2....n-m且长度为m的n-m+1个子串，看看是否有跟模式串匹配的。  
时间复杂度：比对n-m+1次，每次比对m个字符串；时间复杂度O(n\*m)

BF为什么是一个很常用的字符串匹配算法？  
1）实际场景中，n和m都不会很大，而且单次比较中并不需要比较m次，不一样就可以继续下一次了  
2）算法和实现简单，符合KISS（keep it simple and stupid）原则

RK  
针对子串比较需要每个字节比较的效率问题，可以哈希算法对主串中的n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

提高子串哈希值计算的效率  
假设要匹配的字符串的字符集中只包含K个字符，我们可以用一个K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。

继续优化：  
重叠部分可以利用，k进制中k的次幂可以存放到长度为m的数组中重复利用。  
如果只有一个重叠，边计算hash，边比较；已经存在则直接返回  
时间复杂度：  
获取n-m+1次的主串hash值，比较n-m+1次，整体复杂度O(n),问题，刚刚有次幂计算，很容易大于整数范围，所以可以修改hash的算法，如不采用次幂，直接用a=0，b=1....相加,得到结果，此时会存在hash冲突，解决方案为：哈数值相同时，再比较子串是否相等即可。

如果主串和子串是二维数据该如何查找？  
一样算法，横纵下标作为次幂，但是需要循环嵌套。

BM算法--支持每次移动多位  
坏字符串规则:子串倒着匹配，主串中的某个字符无法与模式串匹配，倒序子串，该字符在模式串中的位置为si，与模式串第xi个字符匹配，不匹配为-1；si-xi就为子串右滑的大小。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70][]  
好后缀规则：也是子串倒着匹配，假设子串的部分尾部能与模式串的部分尾部完全匹配，记为好后缀u  
1) 继续查找子串中是否存在u，如果存在则移动子串使其对齐。  
2）如果继续查找子串中不存在u，但是好后缀的后缀子串，如果存在跟模式串的前缀子串匹配的，我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，然后将模式串滑动到合适的位置。  
如下图：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 1][]

如何查找坏字符在模式串中出现的位置呢？  
如果在模式串中顺序遍历查找，会比较低效。我们可以将模式串中的每个字符及其下标都存到散列表中，然后快速定位坏字符串在模式串中的位置。

KMP算法--支持每次移动多位  
模式串和主串比较时，正向逐个字符比较，直到遇到不一致的字符；此时把不匹配的字符仍叫作坏字符，把已经匹配的字符叫作好前缀。如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 2][]

倒叙查找与模式串前缀字符一致的位置；找位置本质上与主串无关，可以先对模式串处理；  
next\[i\]=k； i:前缀结尾字符下标 k:最长可匹配前缀子串结尾字符下标  
如下图：

![20191217102242440.png][]

i =3；  k=2，所以此时主串中指针直接后移两位，如下图：

![20191217102259932.png][]  
next\[i\]=k的推算：  
利用已经计算出来的 next 值，我们是否可以快速推导出 next\[i\] 的值呢？  
假设 next\[i-1\]=k-1，也就是说，子串 b\[0, k-1\] 是 b\[0, i-1\] 的最长可匹配前缀子串。  
1）如果子串 b\[0, k-1\] 的下一个字符 b\[k\]，与 b\[0, i-1\] 的下一个字符 b\[i\] 匹配，那子串 b\[0, k\] 就是 b\[0, i\] 的最长可匹配前缀子串。所以，next\[i\] 等于 k  
2）如果子串 b\[0, k-1\] 的下一个字符 b\[k\]，与 b\[0, i-1\] 的下一个字符 b\[i\]不匹配，那么此时可以考虑次最长可匹配前缀，并判断下一个字符是否相等；相等就是最长可匹配的前缀子串。否则继续找次次最长可匹配前缀。  
java 字符串contains底层算法是什么？  --如下，暴力查找

static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }
        // 首位字符
        char first = target[targetOffset];
        // source需要遍历的最后一位位置，即要求source剩余长度大于targetCount才有可能
        int max = sourceOffset + (sourceCount - targetCount);
    
        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }
            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                // 第二个字符位置，即除第一个字符外的开始比较的位置
                int j = i + 1;
                // 最后个字符位置，即除结束比较的位置
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);
    
                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

BF 模式串一步一步移动，且每次需比较所有字符  
RK 分别求源和目标串的hash值，对hash值比较，避免一个一个字符的比较，还是一步走一步  
BM 坏字符串+好后缀  
KMP 好前缀，并提前获取不同的好前缀移动几步；根据好前缀的后缀与前缀对应关系决定每次移动几步

BF和Rk效果不好，BM和KMP过于复杂，下面给出比较合适的算法：Sunday算法

Sunday算法和BM算法稍有不同的是，Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；  
否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。  
这里移动位数也可以维护一个数组。。。

Sunday算法的缺点  
看上去简单高效非常美好的Sunday算法，也有一些缺点。因为Sunday算法的核心依赖于move数组，而move数组的值则取决于模式串，那么就可能存在模式串构造出很差的move数组。例如下面一个例子  
主串：baaaabaaaabaaaabaaaa  
模式串：aaaaa  
这个模式串使得move\[a\]的值为1，即每次匹配失败时，只让模式串向后移动一位再进行匹配。这样就让Sunday算法的时间复杂度飙升到了O(m\*n)，也就是字符串匹配的最坏情况

作者：houskii  
链接：https://www.jianshu.com/p/2e6eb7386cd3  
来源：简书  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

搜索关键词的提示 一个主串对应对个模式串 -1对n的搜索  
什么是Trie树  
字典树，专门处理字符串匹配的数据结构，解决在一组字符串集合中快速查找某个字符串的  
6 个字符串，它们分别是：how，hi，her，hello，so，see，组成的trie树如下：

Trie树的本质：利用字符串之间公共的前缀，将重复的前缀合并在一起。  
Trie树构造过程图示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 3][]

如何实现一颗Trie树？  
操作：  
1）字符串集合构造成Trie树  
2）查询字符串

二叉树使用左右指针表示树结构，那具有多个分支的树结构怎么表示？  
下标与字符映射的数组来存储子节点的指针。详细如下：  
假设我们的字符串中只有从a到z这 26 个小写字母，我们在数组中下标为 0 的位置，存储指向子节点 a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。  
class TrieNode \{  
  char data;  
  TrieNode children\[26\];  
\}

Tries树为什么耗内存？  
总会有26大小的数组存在，并且每个数组存储一个8子杰的指针；即使一个节点实际只有很少的节点，也要维护长度为26的数组。  
但是

我们可以稍微牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点的子节点指针。用哪种数据结构呢？我们的选择其实有很多，比如有序数组、跳表、散列表、红黑树等。假设我们用有序数组，数组中的指针按照所指向的子节点中的字符的大小顺序排列。查询的时候，我们可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。但是，在往Trie树中插入一个字符串的时候，我们为了维护数组中数据的有序性，就会稍微慢了点。

trie树的问题：  
1 字符串中包含的字符集不能太大，否则占用内存  
2 要求字符串中的前缀重合比较多  
3 需要自己实现相关  
4 使用指针，缓存不友好

一个高性能的敏感词过滤系统呢 ，即一个主串对应多个模式串  
单模式串匹配算法：一个模式串与主串匹配的算法，即仅需要在主串中查找一个模式串；如 BF BM KPM  
多模式串匹配算法:多模式串与主串匹配的算法，如 Trie算法

基于单模式串的敏感词过滤：以KMP为例，每次使用一个敏感词在用户输入内容中查找。有多少个敏感词就查询多少次。  
基于Trie树的敏感词过滤：先根据敏感词构建Trie树，然后将用户输入内容在Trie树中匹配，如果遇到叶子节点或者不匹配的时候，我们将主串的开始位置后移一位，重新在Trie树中匹配。然后需要比较多次

AC自动机：  
基于Trie树，增加失败指针；  
如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 4][]

4 个模式串，分别是 c，bc，bcd，abcd；

当主串(abc)比较的时候，首先进入abc，此时会比较失败，此时会跳转到c的失败指针方向，去比较主串的子串(bc)是否敏感，此时敏感.并且能够充分遵守从大原则，即如果abc和bc都敏感的时候，此时会判定为abc。

public class SundayAlgorithm {
    
        /**
         * desc:  Sunday算法和BM算法稍有不同的是，Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。
         *
         * 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
         * 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。
         */
    
        public static void main(String[] args) {
            char[] origin = "substring searchin".toCharArray();
            char[] target = "searchin".toCharArray();
            System.out.println(search(origin, target));
        }
    
        public static int ASCII_SIZE = 126;
    
        public static int search(char[] origin, char[] target){
            int ol = origin.length;
            int tl = target.length;
    
            // move中存储，不一致发生时，指针应该后移的个数
            int[] move = new int[ASCII_SIZE];
            // 给move设置默认值，target中不存在的字符，直接移动target的长度+1
            for(int i=0; i<ASCII_SIZE; i++){
                move[i] = tl+1;
            }
    
            // 对target中包含的char设置移动位数，即target总长度减去index
            for(int index=0; index<tl; index++){
                move[target[index]] = tl-index;
            }
    
            int oIndex = 0;
            while(oIndex <= ol-tl+1){
                for(int i=oIndex,j=0; j<tl; j++,i++){
                    // 遍历源与目标字符是否一致
                    if(origin[i] != target[j]){
                        // 不一致的时候直接移动指针，定位第一个oIndex+tl，后移目标
                        oIndex += move[origin[oIndex+tl]];
                        break;
                    }
                    if(j == tl-1){
                        return oIndex;
                    }
                }
            }
            return -1;
        }
    }

public class TrieTest {
    
        public static void main(String[] args) {
            System.out.println(getIndex('a'));
            System.out.println(getIndex('b'));
            insert("abc");
            insert("abd");
            search("abd");
            search("aba");
            search("ab");
    
        }
    
        public static Trie root = new Trie('/');
    
        public static  void insert(String str){
            if(str == null || "".equals(str)){
                return;
            }
            char[] chars = str.toCharArray();
            Trie node = root;
            Trie[] children ;
            int charIndex ;
            for(int i =0; i<chars.length; i++){
                children = node.getChildren();
                charIndex = getIndex(chars[i]);
                // 不存在则插入新节点
                if(null == children[charIndex]){
                    children[charIndex] = new Trie(chars[i]);
                }
                // 设置尾部节点
                if(i == chars.length-1){
                    children[charIndex].setEndingChar(true);
                }
                // 指针移动，定位下一节点
                node = children[charIndex];
            }
        }
    
        /**
         * desc: a对应的下标为0，b对应下标为1，依次类推
         */
        public static  int getIndex(char c){
            return c-97;
        }
    
        public static  void search(String str){
            if(str == null || "".equals(str)){
                return;
            }
            char[] chars = str.toCharArray();
    
            Trie node = root;
            Trie[] children;
            int index ;
            for(int i=0; i<chars.length; i++){
                children = node.getChildren();
                index = getIndex(chars[i]);
                if(children[index] == null ){
                    System.out.println(str +" not exist");
                    break;
                }else{
                    node = children[index];
                    // 最后一个节点存在
                    if(i == chars.length-1 ){
                        if(node.isEndingChar){
                            System.out.println(str +" exist");
                        }else{
                            System.out.println(str +" not exist");
                        }
                    }
                }
            }
        }
    
        static class Trie{
            // 此时限定value范围只能是 a-z，便于处理
            char value;
            Trie children[] = new Trie[26];
    
            public boolean isEndingChar() {
                return isEndingChar;
            }
    
            public void setEndingChar(boolean endingChar) {
                isEndingChar = endingChar;
            }
    
            boolean isEndingChar = false;
    
            public Trie(char value){
                this.value = value;
            }
    
            public char getValue() {
                return value;
            }
    
            public void setValue(char value) {
                this.value = value;
            }
    
            public Trie[] getChildren() {
                return children;
            }
    
            public void setChildren(Trie[] children) {
                this.children = children;
            }
        }
    
        static int indexOf(char[] source, int sourceOffset, int sourceCount,
                           char[] target, int targetOffset, int targetCount,
                           int fromIndex) {
            if (fromIndex >= sourceCount) {
                return (targetCount == 0 ? sourceCount : -1);
            }
            if (fromIndex < 0) {
                fromIndex = 0;
            }
            if (targetCount == 0) {
                return fromIndex;
            }
            // 首位字符
            char first = target[targetOffset];
            // source需要遍历的最后一位位置，即要求source剩余长度大于targetCount才有可能
            int max = sourceOffset + (sourceCount - targetCount);
    
            for (int i = sourceOffset + fromIndex; i <= max; i++) {
                /* Look for first character. */
                if (source[i] != first) {
                    while (++i <= max && source[i] != first);
                }
                /* Found first character, now look at the rest of v2 */
                if (i <= max) {
                    // 第二个字符位置，即除第一个字符外的开始比较的位置
                    int j = i + 1;
                    // 最后个字符位置，即除结束比较的位置
                    int end = j + targetCount - 1;
                    for (int k = targetOffset + 1; j < end && source[j]
                            == target[k]; j++, k++);
    
                    if (j == end) {
                        /* Found whole string. */
                        return i - sourceOffset;
                    }
                }
            }
            return -1;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191217102028237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191217102100111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191217102138558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5,size_16,color_FFFFFF,t_70
[20191217102242440.png]: https://img-blog.csdnimg.cn/20191217102242440.png
[20191217102259932.png]: https://img-blog.csdnimg.cn/20191217102259932.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191217102420332.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191217102713598.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5,size_16,color_FFFFFF,t_70