算法——字符串匹配专题

心已赠人 2023-10-03 22:11 88阅读 0赞

**目录**

一. 概述

二. 暴力匹配

三. RabinKarp算法

3.1 算法概述

3.2 算法补充

3.3 设计哈希函数

3.4 代码实现

四. kmp算法

4.1 概述及流程

4.2 next数组求解

--------------------

## 一. 概述 ##

字符串匹配问题即，给定两个字符串str1和str2，例如:

str1: ababa

str2:aba

然后进行**判断str2是否是str1的子串，如果是则返回str2在str1中第一次出现的位置**

这个看似简单的问题，其实其后面蕴藏着的算法却较为复杂，以下我将从易到难，介绍字符串匹配的三种算法。

## 二. 暴力匹配 ##

如题所示，即**定义两个指针，一个指针i遍历str1，另一个指针j指向str2的开头**，若是两个指针所指的内容相同，则一起往后走，如果不相同，则j返回起始位置位置,i返回i+1的位置，代码如下:

public int subString(String str1,String str2){
    //特殊情况判断
     if(str2.length()>str1.length()|| str1==null || str2==null){
                return -1;
            }
            //判断str2是否是str1的子串，并返回第一次出现的位置
            for(int i=0;i<str1.length();i++){
                int j=0;
                int k=i;
                while(str1.charAt(k++)==str2.charAt(j++)){
                    if(j==str2.length()-1){
                        return i;
                    }
                }
            }
            return -1;
        }

这种算法的时间复杂度为:O(N\*M)，其中N为str1的长度，M为str2的长度

这种解法是最为简单的，但是时间复杂度在特殊情况下会比较高

--------------------

## 三. RabinKarp算法 ##

### 3.1 算法概述 ###

使用RabinKarp算法，其主要借助了哈希值来进行比较，那么过程是什么样的呢？

我们先算出str2的哈希值，比如说str2的字符串长度是3，那么我们就遍历str1时，三个三个的计算出哈希值，然后再进行比较。

这种方法的好处是什么呢？就是说在str1中计算哈希值时，我们还是假设str2的长度为3，比如str1中，0-3的哈希值计算出来与str2不相同，**当我们计算1-4的哈希值时，只需要按照哈希函数的规律，扣掉0位置的哈希值，加上4位置的哈希值，即可得到1-4的哈希值**，而这个扣掉和加上的过程是O(1)复杂度，这个过程我们就称之为**滚动哈希,**而利用滚动哈希得到的复杂度为：O(N+M)

--------------------

### 3.2 算法补充 ###

其中一个部分就是要设计好相应的哈希函数，这个方法的缺点就是会发生**哈希碰撞，**即在str2较长较复杂时，此时可能会在str1中，**明明是不同的字符串，算出的却是相同的哈希值**，哈希碰撞是难以避免的，这就是这个方法的缺陷，根据相关数据，通常来说，使用十万个不同的字符串产生的冲突大概是0-3个，而当使用一百万个不同字符串时，产生的冲突数量大概在110个左右。

--------------------

### 3.3 设计哈希函数 ###

在RabinKarp算法中，常用到的哈希函数为: hash=C0+C1\*31+C2\*31^2....

因为每个字符都是有其ASCII值的，其中C0就是字符串0位置上字符的ASCII值，C1即字符串1位置上字符的ASCII值，其过程有点类似于进制计算。

哈希函数的设计如下：

public static long hash(String str){
            long res=0;
            for(int i=0;i<str.length();i++){
                res=31*res+str.charAt(i);
            }
            return res;
        }

--------------------

### 3.4 代码实现 ###

Rabin Karp算法中的难点在于在哈希值计算时如何扣掉一个再加上一个

我们假设: str1="BABABA"

str2="ABA"

A的ASCII码值为:65，B的ASCII码值为:66

则 str2的哈希值计算为： 65\*31^0+66\*31^1+65\*31^2

当我们计算str1中的0-3的三个的哈希值时，其值为: 66\*31^0+65\*31^1+66\*31^2

当我们计算str1中的1-4的三个哈希值时，其值为: 65\*31^0+66\*31^1+65\*31^2

比对0-3和1-4的哈希值计算时，我们可以发现，将0-3的哈希值乘以31，然后加上4位置的哈希值，然后再减去0位置的值乘以31^3(3为str2的长度)

或者也可以，将0-3的哈希值先减去0位置的值后，再除以31，然后加上 4位置的值乘以31^2(2为str2长度减一)

具体滚动过程我们可以使用一个hash\[\]来记录下来，滚动过程代码如下:

public static long[] hash(String str,int M){ //M为str2的长度
            long[] res=new long[str.length()-M];
            //先计算0-M的hash值
            res[0]=hash(str.substring(0,M));
            //开始滚动
            for(int i=M;i<str.length();i++){
                char newChar=str.charAt(i);
                char oldChar=str.charAt(i-M);
                long v=(res[i-M]*31+newChar-(long)Math.pow(31,M)*oldChar)%Long.MAX_VALUE; //%是为了防止溢出
                res[i-M+1]=v;
            }
            return res;
        }

整体代码实现如下：

package com.atguigu.algorithm;
    
    public class RabinKarp2 {
        final static long seed=31;
    
        public static void main(String[] args) {
            String s="ABABABA";
            String p="ABA";
            long[] hash=hash(s,p.length());
            long hash1=hash(p);
            for(int i=0;i<hash.length;i++){
                if(hash[i]==hash1){
                    System.out.println("match:"+i);
                }
            }
        }
        static long hash(String str){
            long hash=0;
            for(int i=0;i<str.length();i++){
                hash=seed*hash+str.charAt(i);
            }
            return hash;
        }
        static long[] hash(String s,int M){
            //利用滚动方法，求取一个hash数组
            long[] res=new long[s.length()-M+1];
            //前m个字符的hash
            res[0]=hash(s.substring(0,M)); //M其实就是短数组的长度
            for(int i=M;i<s.length();i++){
                char newChar=s.charAt(i);
                char oldChar=s.charAt(i-M);
                long v=(res[i-M]*seed+newChar-(long)Math.pow(seed,M)*oldChar)%Long.MAX_VALUE;
                res[i-M+1]=v;
            }
            return res;
        }
    }

--------------------

## 四. kmp算法 ##

### 4.1 概述及流程 ###

kmp算法是一种干练而又强大的字符串匹配算法，其具体原理可以听B站左程云算法p13进行了解，我这里仅进行算法流程和代码的演示。

KMP算法需要一个next数组来进行辅助，这个数组记录的是模式串上对应位置之前的**前缀和后缀的最大匹配长度**。

对于常规的暴力解法来说，i是遍历str1的指针，j是遍历str2的指针，对于传统的暴力解法，当i和j失配，即str1.charAt(i)!=str2.charAt(j)时，**i会回溯到i+1的位置，而j会回溯到0的位置**重新进行匹配。

而引入next数组的意义则是，j并不需要每次都回溯到0位置上，而是回溯到next\[j\]的位置上。

我们假设next数组已经求解出来，则算法的具体代码如下：

public int kmp(String str1,String str2){
            if(str1==null || str2==null|| str1.length()<str2.length()){
                return -1;
            }
            char[] chars1=str1.toCharArray();
            char[] chars2=str2.toCharArray();
            int i1=0;
            int i2=0;
            int[] next=getNextArray(str2);
            while(i1<str1.length() && i2<str2.length()){
                if(chars1[i1]==chars2[i2]){
                    i1++;
                    i2++;
                }else if(next[i2]==-1){  //next数的第0项默认为-1,此时跳到这步说明失配了，同时i2无法再往前跳了，需要i1++换一个开头
                    i1++;
                }else{
                    i2=next[i2]; //失配了进行跳转
                }
            }
            //i1越界或者 i2越界
            return i2==str2.length()?i1-i2:-1;
        }

### 4.2 next数组求解 ###

在进行next数组求解之前，我们先了解一下什么是字符串前缀和后缀的最大匹配长度。

我们以字符串bababb为例：

对于第0位而言，其前面没有字符，故最大匹配长度我们规定为-1

对于第1位而言，前面只有一个字符，最大匹配长度我们记为0

对于2位而言，其前面的字符是 b a,其实前缀只有一个b,后缀只有一个a，并不相等，故最大匹配长度为0

对于第3位而言，其前面的字符为 b a b，当其前后缀长度为2时，其前缀有 ba，对应后缀为ab，并不相等；当其前后缀长度为1时，前缀为b，后缀也为b ，故最大匹配长度为1

对于第4位而言，其前面的字符为 b a b a ，我们可知 其 前缀为 ba,后缀也为ba时有最大匹配长度2

对于第5位而言，其前面字符为 b a b a b ，我们可知其前缀和后缀为bab时有最大匹配长度3

next数组的求解，我们应采用迭代的方式进行求解：

首先，next数组会进行相应的初始化，即

next\[0\]=-1 next\[1\]=0  
![6e0ae8114a8d4067b43cb897714b793b.png][]

如果pj==pk, next\[j+1\]=k+1 或者 k<0,next\[j+1\]=k+1;

否则k继续回溯，直到满足pj==pk 或者 k<0

具体代码如下：

public static int[] next(String str){
            int[] ret=new int[str.length()];
            ret[0]=-1;
            if(str.length()==1){
                return ret;
            }
            ret[1]=0;
            int j=1;
            int k=ret[j];
            while(j<str.length()-1){
                if(k<0 || str.charAt(j)==str.charAt(k)){
                    ret[++j]=++k;
                }else{
                    k=ret[k];
                }
            }
            return ret;
        }

kmp总体代码如下：

package com.atguigu.substring;
    
    public class KMP {
        public int[] getNextArray(String str){
                int[] ret=new int[str.length()];
                ret[0]=-1;
                if(str.length()==1){
                    return ret;
                }
                ret[1]=0;
                int j=1;
                int k=ret[j];
                while(j<str.length()-1){
                    if(k<0 || str.charAt(j)==str.charAt(k)){
                        ret[++j]=++k;
                    }else{
                        k=ret[k];
                    }
                }
                return ret;
            }
        public int kmp(String str1,String str2){
            if(str1==null || str2==null|| str1.length()<str2.length()){
                return -1;
            }
            char[] chars1=str1.toCharArray();
            char[] chars2=str2.toCharArray();
            int i1=0;
            int i2=0;
            int[] next=getNextArray(str2);
            while(i1<str1.length() && i2<str2.length()){
                if(chars1[i1]==chars2[i2]){
                    i1++;
                    i2++;
                }else if(next[i2]==-1){  //next数的第0项默认为-1,此时跳到这步说明失配了，同时i2无法再往前跳了，需要i1++换一个开头
                    i1++;
                }else{
                    i2=next[i2]; //失配了进行跳转
                }
            }
            //i1越界或者 i2越界
            return i2==str2.length()?i1-i2:-1;
        }
    }

[6e0ae8114a8d4067b43cb897714b793b.png]: https://img-blog.csdnimg.cn/6e0ae8114a8d4067b43cb897714b793b.png