vcjmhg 的个人博客

自律者自由

  menu
80 文章
13419 浏览
1 当前访客
ღゝ◡╹)ノ❤️

sunday算法解决字符串匹配问题 置顶!

概述

提起字符串匹配可能更多人会想到 KMP 算法,该算法时间复杂度为 O(m+n),而且也是我们在学习数据结构过程中最早接触到的比较好的算法。但 KMP 算法需要在模式字符串有关联的情况下,也即模式字符串前后缀字符相似度较高的情况下匹配效率比较高。但是在实际应用场景中模式字符串更多情况下是无规律的,因此在工程应用中字符串匹配问题的解决更多的使用的是 sunday 算法。

解题思路

sunday 算法较之于 BM 算法最大的不同点在于 sunday 算法在匹配的过程中主串中参加匹配的最末位字符的下一位字符。

  • 如果末尾的下一位字符(如该字符为'a')没有在模式字符串中出现过,则直接跳到'a'的下一位字符开始新一轮的比较
  • 如果模式字符串中包含'a',则将模式字符串中从左到右中最早出现的字符'a'与源字符串中的'a'对应开始新一轮的匹配

我们下边举一个例子来说明 sunday 算法的匹配过程。比如在一个主串"substring searching"中查找模式串"search"。

  1. 开始时,将模式字符串和主字符串左侧对齐开始进行匹配

img

  1. 在匹配的过程中发现在第二个字符 e 处出现匹配失败的情况。此时我们关注参与匹配的最末尾字符的下一位即 i,由于模式字符串中并没有 i,因此模式字符串直接跳过一大片,向右移动位数 = 模式字符串长度 +1,也即移动到字符 n 的位置。

  1. 在新一轮的匹配过程中发现第一个字符便出现了不匹配的情况。然后我们看到参与匹配的末尾字符的下一位字符为 r,并且 r 存在于模式字符串中因此可以将模式字符串移动 3 位(移动到模式字符串中的 r 和主字符串中的 r 对齐)如下:

img

  1. 在新一轮匹配过程中发现匹配成功,结束匹配返回匹配的位置。

代码

 1class Solution {
 2    //使用sunday算法来求解
 3    public int strStr(String haystack, String needle) {
 4        //边界判断
 5        if(needle.equals("")||needle==null){
 6            return 0;
 7        }
 8        if(haystack==null){
 9            return -1;
10        }
11        char [] haystackArray=haystack.toCharArray();
12        char []needleArray=needle.toCharArray();
13        int haystackLength=haystackArray.length;
14        int needleLength=needleArray.length;
15        //定义偏移数组
16        int move[]=new int[256];
17        //对偏移数组进行初始化工作
18        for(int i=0;i<256;i++){
19            move[i]=needleLength+1;
20        }
21        for(int i=0;i<needleLength;i++){
22            move[needleArray[i]]=needleLength-i;
23        }
24        //模式字符串第一个字符在匹配过程与源字符串对应的未知,j表示当前已经匹配的字符个数
25        int s=0,j=0;
26        //进行匹配
27        while(s<=haystackLength-needleLength){
28            j=0;
29            while(haystackArray[s+j]==needleArray[j]){
30                j++;
31                if(j==needleLength){
32                    return s;
33                }
34            }
35            if(s<haystackLength-needleLength){
36                s+=move[haystackArray[s+needleLength]];
37            }else{
38                return -1;
39            }
40        }
41        return -1;
42    }
43}

标题:sunday算法解决字符串匹配问题
作者:vcjmhg
地址:https://vcjmhg.top/sunday