正文

kmp算法字符串匹配算法(代码片段)

sxw123  sxw123  2023-03-21  345

关键词：

简介

字符串的模式匹配是对字符串的基本操作之一，广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域，如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻找模式串P是否在主串T 中，且其出现的位置。我们对字符串匹配的效率的要求越来越高，应不断地改良模式匹配算法，减少其时间复杂度。

算法说明

设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b

模式串（下文中我们称作W）为：a b a c a b

用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。

而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

在第一次匹配过程中

T: a b a c a a b a c a b a c a b a a b b

W: a b a c a b

在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，其中T[0]~T[4]就是上文中说的已经匹配的模式串子串，移动找出最长的相同的前缀和后缀并使他们重叠：

T: a b a c aa b a c a b a c a b a a b b

W: a b a c a b

然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。

然而，如果每次都要计算最长的相同的前缀反而会浪费时间，所以对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间就成了常数时间。比如：

j	0	1	2	3	4	5
W[j]	a	b	a	c	a	b
F(j)	0	0	1	0	1	1

当W[j]与T[j]不匹配的时候，设置j = F(j-1).

朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下，朱洪的KMP算法比KMP算法更加有效。

假设在执行正文中自位置 i 起“返前”的一段与模式的自右至左的匹配检查中，一旦发现不匹配（不管在什么位置），则去执行由W[m]与t[i]+d(x）起始的自右至左的匹配检查，这里x是字符t。它的效果相当于把模式向右滑过d(ti）一段距离。显然，若ti不在模式中出现或仅仅在模式末端出现，则模式向右滑过的最大的一段距离m。图1.1示出了执行BM算法时的各种情况。实线连接发现不匹配以后要进行比较的正文和模式中的字母，虚线连接BM算法在模式向右滑后正文和模式中应对齐的字母，星号表示正文中的一个字母。

public class StringMatching 
    public static void main(String[] args) 
        //暴力匹配算法
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你";
        int match = violenceMatch(str1, str2);
       // System.out.println(match);

        String s1= "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        String s3 = "ABC";
        int[] next = kmpNext("ABCDABD");//[0,1]
        int res = kMP(s1, s2, next);
        System.out.println(Arrays.toString(next));
        System.out.println(res);

    


    /*暴力匹配算法*/
    public  static  int violenceMatch(String str1,String str2)
      char[] s1 = str1.toCharArray();
      char[] s2 = str2.toCharArray();
      int i=0;//索引指向s1
      int j = 0;//索引指向s2
        while (i<s1.length&&j<s2.length)//匹配不越界
            if (s1[i] ==s2[j])//匹配成功
               i++;
               j++;
            else //不成功
                i = i -(j-1);
                j=0;
            
        
        //判断是否匹配成功
        if (j==s2.length)
            return  i-j;
        else 
            return -1;
        
    

   /*获取到一个字符串的部分匹配值*/
    public static  int[] kmpNext(String dest)
        /*保存部分匹配值*/
        int[] next = new int[dest.length()];
        next[0] = 0;//如果字符串长度为1；部分匹配值是0；
        for (int i = 1 ,j=0; i <dest.length() ; i++) 
            //当不相等时需要从j-1获取新的j
            /*直到发现dest.charAt(i) == dest.charAt(j)退出*/
               while (j>0 &dest.charAt(i) != dest.charAt(j))
                   j=next[j-1];//kmp算法的基础
               
        if (dest.charAt(i) == dest.charAt(j))
            j++;
        
        next[i] =j;
        
        return next;
    

    /*KMP算法查找字符最早出现的位置*/
    public  static  int kMP(String str1,String str2,int[] next)
        for (int i = 0 ,j=0; i <str1.length() ; i++) 

            /*需要考虑str1.charAt(i) ！=str2.charAt(j)时*/
            while (j>0&&str1.charAt(i)!=str2.charAt(j))
                j=next[j-1];
            

            if (str1.charAt(i) ==str2.charAt(j))
                j++;
            
            if (j==str2.length())
                return i - j + 1;
            
        
        return -1;

kmp算法(代码片段)

1.KMP算法介绍在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用... 查看详情

kmp算法(代码片段)

KMP算法KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达... 查看详情

kmp算法(代码片段)

基本介绍KMP算法是一种用于字符串匹配的算法，网上关于kmp的介绍很多，也十分复杂，（其实我也没怎么搞懂）。首先我们还是考虑朴素的匹配，暴力枚举匹配起点，遇到不匹配的点，就直接退出，进行下一个起始点开始的一轮... 查看详情

算法kmp字符串匹配算法(代码片段)

【原理】（1）next数组原理（2）特殊情况的处理（巧妙增设哨兵）（3）递推法构造next[]表【实现代码】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=100;chart[maxn];//textcharp[ 查看详情

java数据结构&算法宁可累死自己,也要卷死别人17kmp算法(代码片段)

...&算法的新篇章.KMP算法KMP(Knuth-Morris-Pratt),是一种改进的字符串匹配算法.KMP算法解决了暴力匹配需要高频回退的问题,KMP算法在匹配上若干字符后,字符串位置不需要回退,从而大大提高效率.如图:举个例子(字符串“abcabcdef”匹配... 查看详情

kmp算法(代码片段)

... 避免从头匹配：最长相同前缀后缀KMP第一个线性的字符串匹配算法。算法的优化就是不做无功用，暴力匹配算法每次不匹配时，会重新开始新匹配。KMP的优化在于，知道查看详情

字符串匹配算法（bf算法&&kmp算法）(代码片段)

字符串匹配算法暴力匹配（BF）算法KMP算法next数组求next数组的练习next数组的优化（nextval数组）练习暴力匹配（BF）算法BF算法，即暴力(BruteForce)算法，是普通的模式匹配算法，BF算法的思想就是... 查看详情

字符串-kmp算法(代码片段)

字符串算法中，字符串匹配是一个非常重要的应用。例如在网页中查找关键词，其实就是在对字符串匹配，也就是看一个主字符串中是否包含了一个子字符串。而KMP算法在字符串匹配方法中一个很著名并且很聪明的算法，当然也... 查看详情

kmp算法(代码片段)

...计算next数组前缀和后缀公共部分的最大长度next数组匹配字符串KMP算法基本思想算法由两部分组成计算ptr每一位及之前的字符串中，前缀和后缀公共部分的最大长度的next数组匹配ptr和str，当ptr失配时，利用next数组，实现ptr的最... 查看详情

kmp算法详解及其java实现(代码片段)

KMP算法，又称作“看猫片”算法（误），是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经... 查看详情

kmp算法（字符串的匹配）(代码片段)

视频参考对于正常的字符串模式匹配，主串长度为m，子串为n，时间复杂度会到达O（m*n），而如果用KMP算法，复杂度将会减少线型时间O（m+n）。设主串为ptr="ababaaababaa";，要比较的子串为a=“aab”； KMP算法用到了next... 查看详情

kmp字符串匹配算法(代码片段)

去年冬天就接触KMP算法了，但是听的不明不白，遇到字符串匹配的题我大都直接使用string中的find解决了，但今天数据结构课又讲了一下，我觉得有必要再来回顾一下。之前看过很多关于KMP的博客，有很多虽然很好，但是要么太... 查看详情

kmp算法(代码片段)

数据结构_串对于串,今天就总结了一个算法,关于字符串的模式匹配问题(重点在于kmp算法).普通的模式匹配算法,当匹配不成功时需要将主串的下标恢复到之前匹配的下一个字符,子串下标置为串首;而kmp算法则不需要重置主串的下标... 查看详情

[模板]kmp算法(代码片段)

...。结果写出来之后一直死循环，最后我还是改回从0读入字符串了。[预先定义被匹配文本串为s1，长度为m；匹配模式串为s2，长度为n]KMP算法在字符串匹配算法中时间复杂度比较优，可以做到在O(m+n)的时间内匹配，相对于无脑暴力... 查看详情

kmp算法(代码片段)

字符串匹配中经常会用到KMP算法。它求解的问题类型是：字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。我们一般的做法是：将一个字符串（长度为n，模式串... 查看详情

字符串模式匹配中的bf算法与kmp算法(代码片段)

博客园的编辑器太难用了。。。。。。。。。。。BF算法即暴力算法，很简单，随便举个栗子：#include<iostream>#include<cstring>usingnamespacestd;//S[]:要匹配的链//T[]:模式串intBFsearch(intstart,charS[],charT[])intslen=strlen(S);inttlen=strlen(T 查看详情

kmp算法(代码片段)

...sp;例子-->移动位数＝已经匹配的字符数－对应匹配部分字符串前缀和后缀共有长度如以上主串中的“abab”和目标串中的“abad”，已经匹配的字符数为3（“aba”），“aba”的前缀为[a,a 查看详情