精华内容
下载资源
问答
  • 字符串匹配算法知多少?

    千次阅读 多人点赞 2021-07-03 10:00:09
    一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢? 想到是很正常的,谁让它那么优秀呢。 BF算法 不要被事物的表面现象所迷惑,这个算法全称:Brute Force,有个拉风的中文名:暴力匹配算法...

    在这里插入图片描述

    一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢?

    想到是很正常的,谁让它那么优秀呢。


    BF算法

    不要被事物的表面现象所迷惑,这个算法全称:Brute Force,有个拉风的中文名:暴力匹配算法。

    能想明白了吧。

    如果模式串长度为 m,主串长度为 n,那在主串中,就会有 n-m+1 个长度为 m 的子串,我们只需要暴力地对比这 n-m+1 个子串与模式串,就可以找出主串与模式串匹配的子串。

    1、从头开始往后遍历匹配;
    2、遇上不对了,就回头,把子串和主串的匹配头后移一位
    3、重复以上。直到找到或确定找不到。
    

    复杂度很高啊,但是在实际开发中也是比较常用的。为什么呢?
    真当天天都有成千上万个字符的主串让我们去匹配吗?一般都比较短,而且,统计意义上,算法执行效率不会真的到M*N的地步。

    理论还是要结合实际的。

    还有另一个原因,就是它好写。当然kmp现在更好写,因为封装好了。
    我说的是类似的场景,没有封装好的函数时候,好写,好改。


    RK算法

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

    有没有方法可以提高哈希算法计算子串哈希值的效率呢?

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

    比如要处理的字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。我们把 a~z 这 26 个字符映射到 0~25 这 26 个数字,a 就表示 0,b 就表示 1,以此类推,z 表示 25。

    在这里插入图片描述

    这里有一个小细节需要注意,那就是 26^(m-1) 这部分的计算,我们可以通过查表的方法来提高效率。我们事先计算好 26^0、26^1、26^2……26^(m-1),并且存储在一个长度为 m 的数组中

    模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1),总共需要比较 n-m+1 个子串的哈希值,所以,这部分的时间复杂度也是 O(n)。所以,RK 算法整体的时间复杂度就是 O(n)。

    但是呢,还有一个很致命的问题,叫做数值过大。
    以幂增的速度是非常快的,用不了多久int就hold不住了啊,那要怎么办?难道我们前面所做的努力都白费了?

    其实不然。
    比方说我们可以改乘为加,当我们匹配到一样的哈希值的时候,再打开子串进行比对,因为相加的话是会有哈西冲突的。

    此外,我们还可以加点优化,一边对主串构建,一边对子串进行匹配,如果一样的话就不继续计算后面的hash了。
    该省的时候就要省,该花的时候就要花。


    编辑器中的全局替换方法:BM算法

    用过吗?比方说要在我这篇博客里找出全部的“主串”这个词,有没有想过其底层的原理?

    这是一个性能优于KMP的算法。

    坏字符

    BM 算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。

    我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符(主串中的字符)

    在这里插入图片描述

    这时候该如何操作呢?我们去子串中寻找这个坏字符,如果找到了,就让两个字符的位置对上,继续往后,如果没有找到,就将整个子串移动到坏字符后面。

    很显然,这会儿没找到。

    在这里插入图片描述

    接下来该怎么滑呢?又是个坏字符。
    但是在子串中找到了那个坏字符,那就将两个字符的位置对上。

    在这里插入图片描述

    模式串中有对应的坏字符时,让模式串中 最靠右 的对应字符与坏字符相对。

    在这里插入图片描述

    但是呢,用这个规则还是不太够用的,有些个特殊情况吧,它会导致不但不会向后滑动模式串,还有可能会倒推、

    比如说主串:kkkkkkkkkkkkkkkkkk,模式串是 akk


    好后缀规则

    在这里插入图片描述

    如果模式串中存在已经匹配成功的好后缀,则把目标串与好后缀对齐,然后从模式串的最尾元素开始往前匹配。

    在这里插入图片描述

    如果无法找到匹配好的后缀,找一个匹配的最长的前缀,让目标串与最长的前缀对齐:
    在这里插入图片描述

    在这里插入图片描述

    如果完全不存在和好后缀匹配的子串,则右移整个模式串


    代码实现

    难顶,我一定会回来的

    // a,b 表示主串和模式串;n,m 表示主串和模式串的长度。
    public int bm(char[] a, int n, char[] b, int m) {
      int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
      generateBC(b, m, bc); // 构建坏字符哈希表
      int[] suffix = new int[m];
      boolean[] prefix = new boolean[m];
      generateGS(b, m, suffix, prefix);
      int i = 0; // j 表示主串与模式串匹配的第一个字符
      while (i <= n - m) {
        int j;
        for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
          if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
        }
        if (j < 0) {
          return i; // 匹配成功,返回主串与模式串第一个匹配的字符的位置
        }
        int x = j - bc[(int)a[i+j]];
        int y = 0;
        if (j < m-1) { // 如果有好后缀的话
          y = moveByGS(j, m, suffix, prefix);
        }
        i = i + Math.max(x, y);
      }
      return -1;
    }
     
    // j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
      int k = m - 1 - j; // 好后缀长度
      if (suffix[k] != -1) return j - suffix[k] +1;
      for (int r = j+2; r <= m-1; ++r) {
        if (prefix[m-r] == true) {
          return r;
        }
      }
      return m;
    }
    

    KMP算法

    【C++】算法集锦(10)通俗讲kmp算法

    展开全文
  • 大多数据结构课本中,涉及的内容即的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • 字符串匹配

    千次阅读 2019-06-27 19:44:14
    主串和模式串 ...几种单模式串匹配算法 BF(暴力)算法 RK算法 BM算法 KMP算法 1. BF(Brute Force)算法 时间复杂度O(n*m),其中n是主串长度,m是模式串长度。 缺陷:忽略了已检测过的文本信息。 2. ...

    基础概念

    • 字符串匹配
      在日常操作电脑中,经常用到查找操作。这里用到很重要的概念就是字符串匹配,所谓字符串匹配就是在主串中搜索模式串是否存在及其存在的位置。
    • 主串模式串
      在字符串A中查找字符串B,那字符串A就是主串,字符串B就是模式串。
      我们把主串的长度记作n,模式串的长度记作m。因为我们是在主串中查找模式串,所以n>m。

    几种单模式串匹配算法

    1. BF(暴力)算法
    2. RK算法
    3. BM算法
    4. KMP算法

    1. BF(Brute Force)算法

    在这里插入图片描述
    时间复杂度O(n*m),其中n是主串长度,m是模式串长度。
    缺陷:忽略了已检测过的文本信息。

    2. RK(Rabin-Karp)算法

    如果模式串长度为m,主串长度为n,那在主串中,就会有n-m+1个长度为m的子串。
    BF算法需要对比n-m+1次,每次对比都需要依次对比m个字符。

    RK算法的思路是:

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

    在这里插入图片描述
    简单的哈希算法,需要遍历子串的每个字符,尽管模式串与子串比较的效率提高了,但是,算法整体的效率并没有提高。

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

    假设字符串中只包含a~z这26个小写字符,我们用二十六进制来表示一个字符串,对 应的哈希值就是二十六进制数转化成十进制的结果。
    在这里插入图片描述
    这种哈希算法有一个特点,在主串中,相邻两个子串的哈希值的计算公式有一定关系。
    在这里插入图片描述
    相邻两个子串s[i-1]和s[i] (i表示子串在主串中的起始位置,子串的长度都为m)。我们可以使用s[i-1]的哈希值很快的计算出s[i]的哈希值。
    在这里插入图片描述
    h[i] = (h[i-1] - 26^(m-1)*(s[i-1]-‘a’)) * 26 + (s[i+m-1] - ‘a’)

    可以提前计算26^(m-1)这部分的值,然后通过查表的方式提高效率。
    在这里插入图片描述
    RK算法包含两部分,计算子串哈希值和模式串哈希值与子串哈希值之间的比较。

    • 第一部分,我们前面也分析了,可以通过设计特殊的哈希算法,只需要扫描一遍主串就能计算出所有子串的哈希值了,所以这部分的时间复杂度是O(n)。
    • 第二部分,模式串哈希值与每个子串哈希值之间的比较的时间复杂度是O(1),总共需要比较n-m+1个子串的哈希值,所以,这部分的时间复杂度也是O(n)。

    所以,RK算法整体的时间复杂度就是O(n)。

    如上这种哈希算法是不会有哈希冲突的,因为我们是基于进制来表示一个字符串的,也就是说,一个字符串与一个二十六进制数一一对应,不同的字符串的哈希值肯定不一样。

    问题:模式串很长,相应的主串中的子串也会很长,通过上面的哈希算法计算得到的哈希值就可能很大,可能会超过了计算机中整型数据可以表示的范围。

    建议:设计数值较小的哈希函数,可能会有哈希冲突。在哈希值相等时,还需再对比一下子串和模式串本身。

    3. BM(Boyer-Moore)算法

    我们把模式串和主串的匹配过程,看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时,BF算法和RK算法的做法是,模式串往后滑动一位,然后从模式 串的第一个字符开始重新匹配。
    在这里插入图片描述
    在这个例子里,主串中的c,在模式串中是不存在的,所以,模式串向后滑动的时候,只要c与模式串有重合,肯定无法匹配。所以,我们可以一次性把模式串往 后多滑动几位,把模式串移动到c的后面。
    在这里插入图片描述
    字符串匹配的关键,就是模式串的如何移动最高效。

    BM算法本质上就是寻找一种规律,使得模式串和主串匹配过程中,当遇到字符不匹配的时候,能够跳过一些肯定不会匹配的情况,将模式串尽量往后多滑动几位。

    BM算法包含两部分

    • 坏字符规则(bad character rule)
    • 好后缀规则(good suffix rule)

    BM算法模式串的匹配方式是从末尾往前倒着匹配。
    在这里插入图片描述

    坏字符规则

    从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符(主串中的字符)。
    在这里插入图片描述

    • 坏字符c在模式串不存在,这个时候,我们可以将模式串直接往后滑动三(模式串长度)位,将模式串滑动到c后面的位置,再从模式串的末尾字符开始比较。
      在这里插入图片描述
    • 坏字符a在模式串中存在,模式串中下标是0的位置也是字符a。这种情况下,我们可以将模式串往后滑动两位,让两个a上下对齐,然后再从模式串的末尾字符开 始,重新匹配。
      在这里插入图片描述
    • 规律:当发生不匹配的时候,我们把坏字符对应的模式串中的字符下标记作si。如果坏字符在模式串中存在,我们把这个坏字符在模式串中的下标记作xi。如果不存在, 我们把xi记作-1。那模式串往后移动的位数就等于si-xi。(注意,我这里说的下标,都是字符在模式串的下标)
      在这里插入图片描述
    • 若xi有多个,选择下标最大的那个,即最靠后的那个。

    利用坏字符规则,BM算法在最好情况下的时间复杂度非常低,是O(n/m)。

    • 比如,主串是aaabaaabaaabaaab,模式串是aaaa。每次比对,模式串都可以直接后移四位,所以,匹配具有类似特点的模式串和主串的时候,BM算法非常高效。

    • 不过,单纯使用坏字符规则还是不够的。因为根据si-xi计算出来的移动位数,有可能是负数,比如主串是aaaaaaaaaaaaaaaa,模式串是baaa。不但不会向后滑动模式串,还有可能倒退。所以,BM算法还需要用到“好后缀规则”。

    好后缀规则

    在这里插入图片描述
    我们把已经匹配的bc叫作好后缀,记作{u}。我们拿它在模式串中查找,如果找到了另一个跟{u}相匹配的子串{u*},那我们就将模式串滑动到子串{u*}与主串 中{u}对齐的位置。
    在这里插入图片描述

    • 若在模式串中找不到另一个等于{u}的子串,我们就直接将模式串,滑动到主串中{u}的后面,因为之前的任何一次往后滑动,都不可能匹配主串中{u}的情况。
      在这里插入图片描述
      当模式串中不存在等于{u}的子串时,直接将模式串滑动到主串{u}的后面。是否有点太过头呢?
      在这里插入图片描述
      如果好后缀在模式串中不存在可匹配的子串,那在我们一步一步往后滑动模式串的过程中。
    • 只要主串中的{u}与模式串有重合,那肯定就无法完全匹配。
    • 但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候,并且重合的部分相等的时候,就有可能会存在完全匹配的情况。
      在这里插入图片描述
      所以,在好后缀模式下,若模式串中找不到和好后缀完全匹配的子串,那么:
    • 先看好后缀在模式串中,是否有另一个匹配的子串
    • 还要考察好后缀的后缀子串,是否存在跟模式串的前缀子串匹配的。
      在这里插入图片描述
      BM算法会分别计算好后缀和坏字符往后滑动的位数,然后取两者中的大者,作为模式串往后滑动的位数。

    BM算法实现

    1.坏字符规则实现

    “坏字符规则”本身不难理解。当遇到坏字符时,要计算往后移动的位数si-xi,其中xi的计算是重点,我们如何求得xi呢?
    如果我们拿坏字符,在模式串中顺序遍历查找,这样就会比较低效,势必影响这个算法的性能。

    • 利用哈希表,将模式串中的每个字符及其下标都存到哈希表中

    假设字符集为256,每个字符大小为1个字节,可用大小为256的数组,记录每个字符在模式串中出现的位置,数组下标对应字符的ASCII码值,数组值为字符在模式串中的下标。
    在这里插入图片描述
    如上过程翻译成代码如下,其中变量b是模式串,m是模式串长度,bc是刚刚讲的哈希表:

    const SIZE int = 256
    
    func generateBC(b []byte, m int, bc []int) {
            for i := 0; i < SIZE; i++ {
                  bc[i] = -1//初始化bc
            }
            for i := 0; i < m; i++ {
                 ascii := int(b[i])//计算b[i]的asccii值
                 bc[ascii] = i
            }
    }
    

    在这里插入图片描述
    单有坏字符规则的BM算法,代码如下:

    func bm(mainStr, modeStr []byte) int {
    	bc := make([]int, SIZE)
    	n := len(mainStr)
    	m := len(modeStr)
    	generateBC(modeStr, m, bc) //构建坏字符哈希
    	i := 0                     //i表示主串与模式串对齐的第一个字符位置
    	for i <= n-m {
    		j := 0
    		for j = m - 1; j >= 0; j-- { //模式串从后往前匹配
    			if mainStr[i+j] != modeStr[j] {
    				break //坏字符对应模式串中的下标是j
    			}
    		}
    		if j < 0 {
    			return i //匹配成功,返回主串与模式串第一个匹配的字符的位置
    		}
    		moveNum := j - bc[int(mainStr[i+j])]
    		if moveNum <= 0 { //坏字符可能产生负数的移位
    			moveNum = 1
    		}
    		i = i + moveNum
    	}
    	return -1
    }
    

    好后缀规则实现

    回顾一下,前面讲过好后缀的处理规则中最核心的内容:

    • 在模式串中,查找跟好后缀匹配的另一个子串;
    • 在好后缀的后缀子串中,查找最长的、能跟模式串前缀子串匹配的后缀子串;

    若这两个操作直接使用“暴力”匹配,会使得BM算法效率不高。而好后缀也是模式串本身的后缀子串,所以在正式匹配之前,可以对模式串做预处理操作,预先计算好模式串中的每个后缀子串,对应的另一个可匹配子串的位置。
    在这里插入图片描述

    • 通过长度可以唯一确定一个后缀子串。

    现在引入suffx数组,数组下标k表示后缀子串的长度,下标对应的数组值表示,在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标位置。
    在这里插入图片描述

    • 若模式串中有多个(大于1个)子串跟后缀子串{u}匹配,那suffix数组中该存储模式串中最靠后的那个子串的起始位置,也就是下标最大的那个子串的起始位置。

    suffx数组可以解决好后缀在模式串中能找到另一个可匹配的情况,但是我们还要在好后缀的后缀子串中,查找最长的能跟模式串前缀子串匹配的后缀子串。

    • 用bool类型的prefix数组,来记录模式串的后缀子串是否能匹配模式串的前缀子串。
      在这里插入图片描述
    • 我们拿下标从0到i的子串(i可以是0到m-2)与整个模式串,求公共后缀子串。
    • 如果公共后缀子串的长度是k,那我们就记录suffix[k]=j(j表示公共后缀子串的起始下标)。
    • 如果j等于0,也就是说,公共后缀子串也是模式串的前缀子串,我们就记录prefix[k]=true。
      在这里插入图片描述
      把suffix数组和prefix数组的计算过程,用代码实现出来,如下所示:
    func generateGS(modeStr []byte, suffix []int, prefix []bool) {
    	m := len(modeStr)
    	for i := 0; i < m; i++ {
    		suffix[i] = -1    //默认是找不到和好后缀匹配的子串
    		prefix[i] = false //初始化
    	}
    	for i := 0; i < m-1; i++ { //modeStr[:i],即前缀子串
    		j := i
    		k := 0                                       //公共后缀子串长度
    		for j >= 0 && modeStr[j] == modeStr[m-k-1] { //与modeStr[:m-1]求公共后缀
    			j--
    			k++
    			suffix[k] = j + 1 //j+1表示公共后缀子串在modeStr[:i]中的起始下标,当有多个{u},suffix[k]会被后来者覆盖
    		}
    		if j == -1 {
    			prefix[k] = true //表示有和后缀子串匹配的前缀子串
    			//cabcabcab的suffix[3]=3,prefix[3]为true
    		}
    	}
    
    }
    

    有了这两个数组后,在模式串和主串匹配过程中,遇到不能匹配字符时,根据好后缀规则,移动过程如下:

    • 假设好后缀的长度是k。我们先拿好后缀,在suffix数组中查找其匹配的子串。
    • 如果suffix[k]不等于-1(-1表示不存在匹配的子串),那我们就将模式串往后移动j- suffix[k]+1位(j表示坏字符对应的模式串中的字符下标)。
      在这里插入图片描述
    • 如果suffix[k]等于-1,表示模式串中不存在另一个跟好后缀匹配的子串片段,可如下处理,注意这时prefix[k]中的k是小于suffix[k]中的k。
      在这里插入图片描述
    • 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串,我们就将整个模式串后移m位。
      在这里插入图片描述
      BM算法的完整版代码如下:
    func bm(mainStr []byte, modeStr []byte) int {
    	bc := make([]int, SIZE)
    	n := len(mainStr)
    	m := len(modeStr)
    	generateBC(modeStr, m, bc) //构建坏字符哈希
    	suffix := make([]int, m)
    	prefix := make([]bool, m)
    	generateGS(modeStr, suffix, prefix)
    	i := 0 //i表示主串与模式串对齐的第一个字符位置
    	for i <= n-m {
    		j := 0
    		for j = m - 1; j >= 0; j-- { //模式串从后往前匹配
    			if mainStr[i+j] != modeStr[j] {
    				break //坏字符对应模式串中的下标是j
    			}
    		}
    		if j < 0 {
    			return i //匹配成功,返回主串与模式串第一个匹配的字符的位置
    		}
    		x := j - bc[int(mainStr[i+j])] //坏字符规则算出来的移动位数
    		y := 0
    		if j < m-1 { //如果有好后缀(j = m-1时,表示没有好后缀)
    			y = moveByGS(j, m, suffix, prefix) //返回好后缀规则下,模式串移动的位数
    		}
    		i = i + mathutil.Max(x, y) //坏字符规则和好后缀规则,取移动位数更多的
    		//这里i一定大于0,因为若无好后缀,bc[int(mainStr[i+j])]为-1,那坏字符规则得到的移动位数一定大于0
    	}
    	return -1
    }
    
    //j表示坏字符对应的模式串中的字符下标,m表示模式串长度
    func moveByGS(j, m int, suffix []int, prefix []bool) int {
    	k := m - 1 - j       //好后缀长度
    	if suffix[k] != -1 { //模式串中存在和好后缀匹配的子串
    		return j - suffix[k] + 1
    	}
    	
    	//这个for循环就是遍历好后缀的后缀子串,看是否存在prefix[m-r]为true的情况
    	for r := j + 2; r <= m-1; r++ {
    		//j+2若为m,此时表示好后缀长度为1,此时移动m位即可
    		if prefix[m-r] == true { //m-r就是好后缀子串的长度
    			return r
    		}
    	}
    	//若好后缀的两个规则都不命中,则移动m位
    	return m
    }
    

    BM算法总结

    • BM算法核心思想是,利用模式串本身的特点,在模式串中某个字符与主串不能匹配的时候,将模式串往后多滑动几位,以此来减少不必要的字符比较,提高匹配的效率。
    • BM算法构建的规则有两类,坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存,为了节省内存,我们可以只用好后缀规则来实现BM算法。

    4. KMP算法

    • KMP算法的核心思想,跟上一节讲的BM算法非常相近。我们假设主串是a,模式串是b。
      在模式串和主串匹配过程中,把不能匹配的那个字符叫作坏字符,把已匹配的那段字符串叫作好前缀。
      在这里插入图片描述
    • 当遇到坏字符的时候,我们就要把模式串往后滑动,在滑动的过程中,只要模式串和好前缀有上下重合,前面几个字符的比较,就相当于拿好前缀的后缀子串,跟模式串的前缀子串在比较
      在这里插入图片描述
      KMP算法试图在模式串和主串匹配的过程中,当遇到坏字符后,对于已经比对过的好前缀,能否找到一种规律,将模式串一次性滑动很多位?
    • 我们只需要拿好前缀本身,在它的后缀子串中,查找最长的那个可以跟好前缀的前缀子串匹配的。
    • 假设最长的可匹配的那部分前缀子串是{v},长度是k。我们把模式串一次性往后滑动j-k位,相当于,每次遇到坏字符的时候,我们就把j更新为k,i不变,然后继续比较。
      在这里插入图片描述
    • 我们把好前缀的所有后缀子串中,最长的可匹配前缀子串的那个后缀子串,叫作最长可匹配后缀子串;对应的前缀子串,叫作最长可匹配前缀子串。
      在这里插入图片描述
    • 求好前缀的最长可匹配前缀子串和后缀子串时,只涉及模式串本身,因此可以预先处理。

    KMP算法提前构建一个数组,用来存储模式串中每个前缀(这些前缀都有可能是好前缀)的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为next数组。

    • 数组下标是每个前缀结尾字符下标,数组值是这个前缀的最长可匹配前缀子串的结尾字符下标
      在这里插入图片描述
    • 笨的方法,比如要计算下面这个模式串b的next[4],我们就把b[0, 4]的所有后缀子串,从长到短找出来,依次看看,是否能跟模式串的前缀子串匹配。很显然,这个方法也可以计算得到next数组,但是效率非常低。
      在这里插入图片描述
    如何高效计算next数组?
    • 假设next[i-1]=k,即b[0,k-1]是b[0,i-1]的最长可匹配前缀子串,如果b[0,k-1]的下一个字符b[k]与b[0,i-1]的下一个字符b[i]匹配,那子串b[0,k]就是b[0,i]的最长可匹配前缀子串,所以next[i]=k。
      在这里插入图片描述
    • 若b[0, k-1]的下一字符b[k]跟b[0, i-1]的下一个字符b[i]不相等呢?查看b[0,i-1]的次长可匹配前缀子串的下一个字符是否等于b[i],依次找下去
      在这里插入图片描述
      KMP算法代码完整版如下:
    func getNext(modeStr []byte) []int {
    	m := len(modeStr)
    	next := make([]int, m)
    	next[0] = -1 //表示好前缀长度为1,无后缀,next[0]为-1
    	k := -1      //初始为-1,表示最开始匹配时,无好前缀一说,还是要逐个字符匹配
    	for i := 1; i < m; i++ {
    		//如下这个for循环,即非简单+1的情况下,依次找next[k]的最长可匹配前缀子串的结尾字符下标
    		for k != -1 && modeStr[k+1] != modeStr[i] { //k!=-1表示当前已有好前缀
    			k = next[k]  //相当于求modeStr[:k]的最长可匹配前缀子串
    			//为什么是k=next[k],从上图看,y即是这里的k,已知next[i-1]=k,求next[i]
    			//因为modeStr[k+1]不等于modeStr[i],故只能看modeStr[:x](x取值为k-1到0)是否与modeStr[i-x:i]是否匹配
    			//常规操作是比较modeStr[k-1]是否等于modeStr[i],若不等,再看k-2,依次顺序比较
    			//假设modeStr[k-1]等于modeStr[i],那么还要看modeStr[:k-2]是否匹配modeStr[i-k+1:i-1],若不满足
    			//则不行,还得往下找,既然一定要满足这个条件,那么可以利用next[k]求出下一个
    			//最长可匹配前缀子串的位置,再比对下一个字符是否等于modeStr[i]
    		}
    		//如下情况,要么是k=-1,要么是modeStr[k+1] == modeStr[i]
    		if modeStr[k+1] == modeStr[i] {
    			k++
    		}
    		next[i] = k
    	}
    	return next
    }
    
    func kmp(mainStr, modeStr []byte) int {
    	n := len(mainStr)
    	m := len(modeStr)
    	next := getNext(modeStr)
    	j := 0
    	for i := 0; i < n; i++ { //i代表主串中与模式串首字符对齐的位置
    		for j > 0 && mainStr[i] != modeStr[j] {
    			j = next[j-1] + 1 //更新j为模式串下次开始匹配的字符位置
    			//next[j-1]表示当前好前缀是modeStr[:j-1]
    		}
    		if mainStr[i] == modeStr[j] { //j代表模式串中坏字符位置
    			j++
    		}
    		if j == m { //主串中找到匹配串
    			return i - m + 1
    		}
    	}
    	return -1
    }
    

    KMP算法总结

    • next数组计算的时间复杂度是O(m)
    • 匹配过程的时间复杂度是O(n)
    • KMP算法的时间复杂度是O(n+m)

    总结

    • BF算法是最简单、粗暴的字符串匹配算法,时间复杂度也比较高,是O(n*m),n、m表示主串和模式串的长度。不过,在实际的软件开发中,因为这种算法实现简单,对于处理小规模的字符串匹配很好用。
    • BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,有实验统计,它的性能是著名的KMP算法的3到4倍。

    leetcode字符串习题

    https://leetcode-cn.com/tag/string/

    展开全文
  • 字符串匹配之暴力匹配

    千次阅读 2018-04-05 16:48:29
    字符串匹配之暴力匹配 字符串匹配就是在一个字符串集里面找到某个模式串出现的所有位置。 例如,找出模式P=abaaP=abaaP=abaa在文本T=abcabaabcabacT=abcabaabcabacT=abcabaabcabac中的位置,用mmm和nnn分别表示PPP...

    字符串匹配之暴力匹配

    字符串匹配就是在一个字符串集里面找到某个模式串出现的所有位置。
    例如,找出模式 P=abaa P = a b a a 在文本 T=abcabaabcabac T = a b c a b a a b c a b a c 中的位置,用 m m n分别表示 P P T的长度, S S 表示当字符串匹配时的有效偏移。

    这里写图片描述

    暴力匹配的方法是通过循环,找出所有的有效偏移S,该循环对每一个可能的 S S 进行检测,看是否满足条件P[1..m]=T[s+1..s+m]

    这里写图片描述

    这种匹配方式可以看做是 P P 字符串在一格一格的滑动,每滑到一个新的位置,需要重新从字符串P头部开始匹配,检查与 T T 文本对应的位置是否相等

    代码;

    void NaiveSearch(const char* T,const char* P)
    {
        int n = strlen(T);
        int m = strlen(P);
        for (int s = 0; s < n - m+1; ++s)
        {
            int i = s, j = 0;
            for (;j < m-1;)
            {
                if (T[i] == P[j]) ++i, ++j;
                else break;
            }
            if (T[i] == P[j])
                printf("%d\n",s);       
        }
    }

    上述代码中,第5行的for循环检查了每一个可能的偏移值S,第8~12行检查了偏移后对应的两个串是否相等,第14行打印出每个合格的偏移量 S S

    暴力匹配在最坏的情况下运行时间为O((nm+1)m),简化为 O(n2) O ( n 2 ) ,例如在 Taaaaaaab T = a a a a a a a b 里面查找 Paaab P = a a a b ,每一次滑动都要完全比较 P P <script type="math/tex" id="MathJax-Element-34">P</script>里面的字符 ,做了很多重复的动作,效率很低。

    参考资料:《算法导论》

    展开全文
  • 字符串匹配算法综述

    万次阅读 多人点赞 2018-07-22 21:39:23
    字符串匹配算法综述 字符串匹配算法综述:BF、RK、KMP、BM、Sunday 字符串匹配算法,是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目。此算法通常输入为原字符串(string)和子串(pattern),要求...
  • 最近在写一个程序,需要用到字符串匹配,并且返回匹配的字符串,C语言库函数中的strtstr无法满足我的要求,只能自己写了。 代码如下 //string match function char *matchString(const char* buf, const char* sub) ...
  • 字符串匹配 -- 朴素字符串匹配算法

    千次阅读 2013-07-26 11:29:51
    朴素字符串匹配算法 参考资料:算法导论 朴素字符串匹配 它用一个循环来找出所有有效位移,该循环对 n - m + 1 个可能的每一个 s 值检查条件 P [ 1.. m ] = T [ s+ 1 .. s + m ] 。 这种朴素的字符串匹配过程可以...
  • 字符串匹配(多模式匹配篇)

    千次阅读 2018-05-12 22:39:22
    字符串匹配(多模式匹配篇)摘要:问题的提出:众所周知,KMP算法在O(n)的时间中solve单模式串匹配问题。但怎样solve多模式串匹配问题呢?Solve:本文用简要记叙了使用trie树,trie图(AC自动机)solve该问题的...
  • iOS之字符串截取、iOS 字符串替换、iOS字符串分隔、iOS之字符串匹配、截取字符串、匹配字符串、分隔字符串 1.iOS 字符串截取 //1.ios截取字符串 NSString *string =@"123456d890"; NSString *str1 = ...
  • 字符串匹配这样一个功能,我想对于任何一个开发工程师来说,应该都不会陌生。我们用的最多的就是编程语言提供的字符串查找函数,比如Java中的 indexOf(),Python 中的find()函数等,它们底层就是依赖接下来要讲的...
  • 字符串匹配算法

    千次阅读 2018-11-05 17:58:47
    网络信息中充满大量的字符串,对信息的搜寻至关重要,因此子字符串查找(即字符串匹配)是使用频率非常高的操作:给定一段长度为N的文本和长度为M的模式字符串(N≥M),在文本中找到一个和模式串相匹配的子串。...
  • 字符串匹配——Sunday算法

    万次阅读 多人点赞 2016-07-08 13:03:34
    字符串匹配——Sunday算法基本思想及举例Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似:1只不过Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。...
  • 引言字符串匹配是数据库开发和文字处理软件的关键。幸运的是所有现代编程语言和字符串库函数,帮助我们的日常工作。不过理解他们的原理还是比较重要的。字符串算法主要可以分为几类。字符串匹配就是其中之一。当我们...
  • Tcl的字符串操作:字符串匹配

    千次阅读 2019-04-07 16:15:04
    所谓字符串匹配是指检测待测字符串(也可称为目标字符串)是否与给定的模式相匹配。这里的模式其实也是字符串;Tcl提供了两种字符串匹配方法:一种为通配符模式,一种为正则表达式。这里先介绍较为简单易用的通配符...
  • Java实现 LeetCode 686 重复叠加字符串匹配

    万次阅读 多人点赞 2020-04-04 21:42:48
    686. 重复叠加字符串匹配 给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。 举个例子,A = “abcd”,B = “cdabcdab”。 答案为 3, 因为 A ...
  • 字符串匹配算法(单模式串)

    千次阅读 2019-02-17 22:37:22
    本文是数据结构与算法之美的学习笔记 ...字符串的匹配算法有:单模式串匹配算法(BF算法,RK算法,BM算法,KMP算法), 多模式串匹配算法(Trie树,AC自动机) BF(Brute Force)算法 基础概念:如果我...
  • 字符串匹配算法-KMP

    千次阅读 2020-03-08 14:30:17
    文章目录字符串匹配问题KMP算法简介前缀/后缀/部分匹配表甲的疑问1:k = next[k-1]是什么鬼?结论得到部分匹配表后匹配过程算法总结 字符串匹配问题 引用知乎用户灵茶山艾府的举例,假设我们有两个角色,甲和乙 甲:...
  • Java实现 蓝桥杯 算法提高 字符串匹配

    万次阅读 多人点赞 2020-04-23 18:25:05
    试题 算法提高 字符串匹配 问题描述  给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,...
  • 字符串匹配算法(多模式串)

    千次阅读 2019-02-23 22:35:40
    上一篇了解了单模式串匹配算法,现在来学习多模式串匹配算法,首先需要了解Trie树 Trie树的概念 Trie树也叫字典树或者前缀树,它是一个树形的结构。是一种专门用来处理字符串匹配的数据结构,用来解决在一组字符串中...
  • 字符串匹配原理及实现(C++版)

    千次阅读 多人点赞 2018-12-05 16:09:01
    字符串匹配原理及实现(C++版)1. 字符串匹配概念2. BF3. KMP4. BM5. 性能总结 1. 字符串匹配概念 2. BF 3. KMP 4. BM 5. 性能总结
  • Python字符串匹配

    千次阅读 2017-11-16 11:10:34
    Python中re模块提供了字符串匹配的函数,常用函数如下: 1.re.match()这个函数描述如下: match(pattern , string , [, flags]) 检查string的开头是否有字符与pattern匹配。如果成功则返回MatchObject,失败则...
  • Python 字符串匹配、搜索及替换

    千次阅读 2019-12-31 23:11:45
    文章目录字符串匹配、搜索及替换字符串开头或结尾匹配str.startswith() 和 str.endswith()用 Shell 通配符匹配字符串fnmatch() 和 fnmatchcase()字符串匹配和搜索 字符串匹配、搜索及替换 字符串开头或结尾匹配 ...
  • 字符串匹配——BMH算法

    千次阅读 2016-07-07 22:45:54
    字符串匹配——BMH算法给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。这样的问题就是字符串匹配问题,这里给出BMH算法的思想。设主串T的长度为n,模式串P的长度为m。BMH(Boyer-Moore-...
  • 字符串匹配——枚举法

    千次阅读 2016-06-14 13:34:07
    字符串匹配——枚举法给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。这样的问题就是字符串匹配问题,这里先给出枚举法的思想。设主串T的长度为n,模式串P的长度为m。主串从0到n-m,每次...
  • 实现朴素的字符串匹配

    千次阅读 2020-04-14 22:46:37
    在一个长字符串中寻找一个短字符串出现的位置,这是字符串匹配问题。 例如:长字符串是 “string” ,短字符串是 “ring” ,那么短字符串在长字符串中出现的位置是 2 ,即 “ring” 在 “string” 中出现的开始位置...
  • FuzzyWuzzy:Python中的模糊字符串匹配

    万次阅读 2019-03-13 16:25:07
    什么是模糊字符串匹配? 模糊字符串匹配是大致(而不是精确地)查找与给定模糊匹配的字符串的过程,就像字面意思一样,它也被称为近似字符串匹配。通常,这些字符串普哦诶的模式另一个字符串。 使用Levenshtein ...
  • Python实现字符串匹配算法

    千次阅读 2015-01-04 16:17:15
    字符串匹配是一个经典的问题,即如何在一个给定的z字符串中查找一个给定的值。这里给出了最原始的蛮力字符串匹配算法以及Horspool算法的实现,后者是利用时空权衡中输入增强技术对原始的蛮力算法进行改进。
  • 【算法】字符串匹配之KMP算法

    千次阅读 2020-07-03 16:56:55
    对于字符串匹配,暴力法是对每个位置进行逐位匹配,只要有匹配失败的,就从待匹配串的下个位置开始从头匹配,这样的时间复杂度是O(MN)。 KMP算法能解决这样效率低下匹配,其核心思想是保留已匹配的前缀和,避免...
  • Java字符串匹配相似度算法

    千次阅读 2018-12-19 11:34:50
    * 采用动态规划的方法(字符串匹配相似度) * @param source 源 * @param target 要匹配的字符串 * @return */ public static int EditDistance(String source, String target) { char[] source...
  • Java实现字符串匹配

    万次阅读 多人点赞 2019-07-20 21:29:47
    1 问题描述 给定一个n个字符组成的(称为文本),一个m(m <= n)的(称为模式),从文本中寻找匹配模式的子串。... //根据文本N,和模式M,返回第一个匹配模式的子串在N中的位置 public...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,008,519
精华内容 403,407
关键字:

串的匹配