KMP算法原理
创始人
2024-06-01 21:04:35
0

所有下标从0开始

子串的定位操作通常称为串的模式匹配,它求的是子串(或称模式串)在主串中的位置。

前缀:除最后一个字符外,字符串的所有头部子串。
后缀:除第一个字符外,字符串的所有尾部子串。
部分匹配值:字符串的前缀和后缀的最长相等前后缀长度。

字符串前缀后缀部分匹配值
a{}{}0
ab{a}{b}0
aba{a, ab}{a, ba}1
abab{a, ab, aba}{b, ab, bab}2
ababa{a, ab, aba, abab}{a, ba, aba, baba}3

暴力匹配O(mn):匹配失败后,模式串指针j回退到初始位置(0),主串指针i回退到本轮匹配初始位置的下一个位置(3 + 1=4)。
KMP算法O(m+n):根据模式串中已成功匹配子串(abcab)的特点,不需要全部回退,i保持不动,j回退到已成功匹配子串的最长相等前缀的下一个位置即可(ab后面的c的位置,即下标2)。因此,我们可以建立一个和模式串等长的数组next,存储j位置匹配失败时j的下一个位置。next[j]的值为pattern[1 ~ j-1]的部分匹配值,即最长相等前缀 或 最长相等后缀 的长度。

采用数学归纳法:

  1. next[0] = -1; // 模式串第0个匹配失败,i不动,赋值j=-1,则++i;++j后等效于模式串第0个字符与主串下一个字符相比。

  2. 设next[i] = j;

    则pattern[0 ~ i-1]中,最长相等前缀为pattern[0 ~ j-1],最长相等后缀为pattern[i-j ~ i-1];

    因此,pattern[0~i]最长相等前后缀 只需比较 pattern[0 ~ j] 和 pattern[i-j ~ i] 即可(最长相等前后缀各向后扩一个)。

    // pattern[0~i] 可能达到的 最长相等前后缀 即为 pattern[0 ~ j] 和 pattern[i-j ~ i],要求pattern[j] == pattern[i]
    // 若pattern[j] != pattern[i],则问题转变为 pattern[0 ~ j]为模式串 和 pattern[i-j ~ i]为主串的 匹配问题
    // (pattern[0 ~ j-1] 和 pattern[i-j ~ i-1]已成功匹配,且pattern[j] != pattern[i],则模式串 指针 应该根据next数组前跳)while (j !=-1 && pattern[i] != pattern[j])j = next[j]; // j < i,next[i]之前即next[0 ~ i-1]已求得
    next[i + 1] = j + 1;
    

  3. 还有一个问题,text[i]和pattern[j]匹配失败,j=next[j],新的pattern[j]或和老的pattern[j]相等,则又要重新跳转,因此,我们应该保证pattern[j] != pattern[next[j]]

    while (j !=-1 && pattern[i] != pattern[j])j = next[j]; // j < i,next[i]之前即next[0 ~ i-1]已求得
    if (pattern[i + 1] == pattern[j + 1])next[i + 1] = next[j + 1]; // 不用递归跳转,因为next是依次加入的,若 pattern[j + 1] == pattern[next[j + 1]],则将跳转使得其不相等,所以pattern[i+1]不可能连续等于pattern[j + 1]和pattern[next[j + 1]]
    elsenext[i + 1] = j + 1;
    
import java.util.Random;public class Main {// 生成随机字符串public static String randomString(String range, int length) {Random random=new Random();StringBuffer sb=new StringBuffer();for (int i = 0; i < length; i++) {sb.append(range.charAt(random.nextInt(range.length())));}return sb.toString();}public static void main(String[] args) {for (int i = 0; i < 1000; i++) {String text = randomString("abcdefg", 1000);String pattern = "abc";int ref = text.indexOf(pattern);int out = indexOf(text, pattern);int kmp = indexOfByKMP(text, pattern);System.out.printf("ref: %10d, out: %10d, kmp: %10d\n", ref, out, kmp);assert ref == out;assert ref == kmp;}}// 暴力匹配public static int indexOf(String text, String pattern) {int i = 0, j = 0;while (i < text.length() && j < pattern.length()) {if (text.charAt(i) == pattern.charAt(j)) {++i;++j;} else {i = i - j + 1;j = 0;}}if (j == pattern.length())return i - pattern.length();elsereturn -1;}private static int[] getNext(String pattern) {int[] next = new int[pattern.length()];int i = 0, j = -1;next[i] = j;while (i < pattern.length() - 1) {if (j != -1 && pattern.charAt(i) != pattern.charAt(j))j = next[j];++i;++j;if (pattern.charAt(i) == pattern.charAt(j))next[i] = next[j];elsenext[i] = j;}return next;}// KMP算法public static int indexOfByKMP(String text, String pattern) {int[] next = getNext(pattern);int i = 0, j = 0;while (i < text.length() && j < pattern.length()) {if (j == -1 || text.charAt(i) == pattern.charAt(j)) {++i;++j;} else {j = next[j];}}if (j == pattern.length())return i - pattern.length();elsereturn -1;}
}

相关内容

热门资讯

安卓系统对比骁龙,性能与生态的... 你有没有想过,为什么你的手机里装的是安卓系统,而不是苹果的iOS呢?又或者,为什么你的安卓手机里搭载...
qt程序安卓系统运行,基于Qt... 你有没有想过,为什么有些手机上的程序运行得那么顺畅,而有些却总是卡得让人抓狂?今天,就让我来给你揭秘...
安卓系统免费应用推荐,助你畅享... 手机里的应用是不是越来越多,有时候都挑花眼了呢?别急,今天我就来给你推荐一些安卓系统上的免费应用,让...
安卓系统视频通话app,打造无... 你有没有发现,现在手机上的视频通话功能越来越强大了?尤其是安卓系统上的那些视频通话app,简直让人爱...
安卓系统发现高危病毒,守护手机... 亲爱的手机用户们,最近可是有个大消息在安卓系统用户群里炸开了锅!没错,就是安卓系统发现了一款高危病毒...
安卓系统疯狂弹广告,揭秘广告软... 你有没有遇到过这种情况?手机里突然弹出一个广告,让你瞬间心情大崩溃?没错,说的就是安卓系统那让人头疼...
ebook 10进入安卓系统 你有没有发现,最近你的安卓手机里多了一个新伙伴——那就是电子书(ebook)10!没错,就是那个我们...
安卓系统如何调听筒,安卓系统调... 手机听筒声音突然变小了?别急,让我来教你如何轻松调教安卓系统的听筒,让它重新恢复活力!一、检查音量设...
安卓系统是怎么手机,解锁智能生... 你有没有想过,我们每天不离手的安卓手机,它背后的安卓系统究竟是怎么一回事呢?今天,就让我带你一探究竟...
安卓系统能代替windows系... 你有没有想过,我们日常使用的安卓系统和Windows系统,哪个才是真正的霸主呢?是不是有时候觉得安卓...
lp108安卓系统,功能特点与... 你有没有听说最近LP108安卓系统火得一塌糊涂?没错,就是那个让无数手机用户都为之疯狂的新系统!今天...
安卓系统挂载u盘,轻松实现数据... 你有没有想过,你的安卓手机或平板电脑突然变成了一个移动的U盘?没错,就是那种可以随意存取文件的神奇设...
i5 安卓系统,引领智能终端新... 你有没有想过,为什么你的手机总是卡得要命,而别人的手机却能流畅如丝?是不是因为你的手机搭载了那个传说...
安卓手机系统没有升级,揭秘潜在... 你有没有发现,你的安卓手机系统好像好久没升级了呢?是不是觉得有点out了?别急,今天就来给你详细聊聊...
安卓14系统定制v,创新功能与... 你知道吗?最近安卓系统又出新花样了!安卓14系统定制版V,这名字听起来就让人兴奋不已。今天,就让我带...
手机安卓系统越高越好,探索最新... 你有没有发现,每次手机更新系统,你的手机就像脱胎换骨了一样?没错,说的就是你,那个安卓手机!今天,咱...
鸿蒙系统怎么用回安卓,轻松实现... 你是不是也和我一样,对鸿蒙系统的新鲜感还没过,却又忍不住想回到熟悉的安卓世界?别急,今天就来手把手教...
苹果7跟安卓系统,性能对决与用... 你有没有想过,为什么苹果7那么受欢迎,而安卓系统却有着庞大的用户群体?今天,我们就来聊聊这个话题,看...
安卓手机刷简化系统,轻松实现流... 你有没有想过,你的安卓手机其实可以变得更加轻快、流畅呢?没错,就是通过刷简化系统!今天,就让我带你一...
社保掌上通安卓系统,轻松掌握在... 你有没有发现,现在的生活越来越离不开手机了?无论是购物、聊天还是办公,手机都能轻松搞定。这不,今天就...