做网站一屏有多大,wordpress商城模板源码,WordPress文字黑条,做网站一般都选哪家28.找出字符串中第一个匹配项的下标 目录 28.找出字符串中第一个匹配项的下标题目描述解法一#xff1a;朴素的模式匹配解法二#xff1a;KMP算法KMP解决的问题类型最长公共前后缀KMP算法过程next数组的构建代码实现 题目描述
给你两个字符串haystack和needle#xff0c;请…28.找出字符串中第一个匹配项的下标 目录 28.找出字符串中第一个匹配项的下标题目描述解法一朴素的模式匹配解法二KMP算法KMP解决的问题类型最长公共前后缀KMP算法过程next数组的构建代码实现 题目描述
给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串的第一个匹配项的下标下标从0开始。
如果needle不是haystack的一部分则返回-1。 解法一朴素的模式匹配
第一种容易想到的方法就是暴力求解法也叫做朴素的模式匹配
简单的来说就是从主串hyastack和子串needle的第一个字符开始将两字符串的字符一一对比如果出现某个字符不匹配主串haystack回溯到第二个字符子串needle回溯到第一个字符再进行一一对比如果再次出现某个字符不匹配则主串回溯到第三个字符子串回溯到第一个字符…以此类推直到子串t的字符全部匹配成功。
这道题目最为直观的解法是依次枚举haystack中的每个字符作为[发起点]每次从原串(haystack)的[发起点]和匹配串needle的[首位]开始尝试匹配
匹配成功返回本次匹配的原串的[发起点]匹配失败枚举原串的下一个[发起点]重新尝试匹配 public int strStr(String haystack, String needle) {int n haystack.length();int m needle.length();for(int i0;imn;i){boolean flag true;for(int j0;jm;j){if(haystack.charAt(ij)!needle.charAt(j)){flag false;break;}}if(flag){return i;}}return -1;}解法二KMP算法 当出现经典的字符串匹配时我们选择使用KMP算法。 KMP解决的问题类型
kmp算法的作用是在一个已知字符串中查找子串的位置也叫做串的模式匹配。
比如主串s“university”子串t“sit”。现在我们要找到子串t在主串s中的位置这点相信大家很容易就看出来了是在第七个位置。
当然在字符串非常少的时候“肉眼观察法”不失为一个好方法但如果要你在一千行一万行文本中找一个单词我觉得一般人都找不到。
第一种容易想到的方法就是刚刚的解法一暴力求解法也叫做朴素的模式匹配 简单的来说就是从主串s和子串t的第一个字符开始将两字符串的字符一一对比如果出现某个字符不匹配主串s回溯到第二个字符子串t回溯到第一个字符再进行一一对比如果再次出现某个字符不匹配则主串s回溯到第三个字符子串s回溯到第一个字符…以此类推直到子串t的字符全部匹配成功。 但是这个方法真的很慢因为求一个子串的位置需要太多步骤而且很多步骤根本没必要。
这种暴力解法在最好的情况下算法的时间复杂度为O(n)即子串的n个字符正好等于主串的前n个字符而最坏的情况下时间复杂度为O(n*m)。但是好在这种算法的空间复杂度为O1即不消耗空间而消耗时间。
下面进入正题KMP算法是如何优化这些步骤的。
其实KMP算法的主要思想就是牺牲空间换时间。
我们回头看一遍解法一的暴力方式为什么这么慢呢是因为我们回溯的步骤太多了所以我们应该减少回溯的次数。
怎样做呢比如上面第一个图当字符’d’与’g’不匹配我们保持主串的指向不变
主串依然指向’d’而把子串进行回溯让’d’与子串中’g’之前的字符再进行比对。
如果字符匹配则主串和子串字符同时右移。
至于子串回溯到哪个字符这个问题我们先放一放。
最长公共前后缀
这里提出一个概念字符串的最长相等前缀和后缀
举个例子
字符串abcdab
前缀的集合{aababcabcdabcda}
后缀的集合{babdabcdabbcdab}
此时最长的公共前后缀就是ab
OK现在我们已经会求一个字符串的前缀后缀以及公共前后缀了这个概念很重要。
之前留了一个问题子串回溯到哪个字符现在可以着手解决了
KMP算法过程
现在我们看一个图第一个长条代表主串第二个长条代表子串红色部分代表两串中已匹配的部分
绿色和蓝色部分分别代表主串和子串中不匹配的字符 现在发现了不匹配的地方我们根据KMP算法的思想保持主串位置不动将子串向后移现在我们要解决的就是移动多少的问题
之前提到的最长公共前后缀的概念有用处了。
因为红色部分即已经匹配的部分也会有最长相等前后缀如下图 我们发现之前“abcab”红色部分的最长公共前后缀为“ab”所以我们把前缀“ab”和后缀“ab”都标成灰色
子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐 这一步弄懂了KMP算法的精髓我们就掌握了接下来的流程就是一个简单的循环过程。
事实上每一个字符前的字符串都有最长相等前后缀而且最长相等前后缀的长度是我们移位的关键所以我们单独使用一个next数组存储子串的最长相等前后缀的长度而且next数组的数值只与子串本身有关。
所以next[i]j的含义是下标为i的字符前的字符串最长相等前后缀的长度为j。
我们可以算出上图中子串“abcabcmn”的next数组为next[0]-1前面没有字符串单独处理
字符abcabcmn下标i01234567next[i]-10001230
再看一眼刚刚是哪里出现了不匹配 即s[5]!t[5]
我们把子串移动也就是让s[5]与t[5]前面字符串的最长相等前缀的后一个字符再比较而next[5] 2所以我们让子串t的第三个字符和刚刚主串的位置对齐开始比较 以此类推直到将子串匹配完为止
这里我们可以总结一下next数组的作用
1、next[i]的值表示下标为i的字符前的字符串的最长相等先后缀的长度2、表示该处字符不匹配时应该回溯到的字符的下标
next数组的构建
接下来我们来看看next数组是如何被预设出来的。
假设有匹配串aaabbab对应的next数组构建过程如下 代码实现 public int strStr(String haystack, String needle) {if(needle.isEmpty()){return 0;}//分别读取原串和匹配串的长度int n haystack.length(),m needle.length();//原串和匹配串前面都加空格使其下标从1开始haystack haystack;needle needle;//转成字符数组char[] s haystack.toCharArray();char[] p needle.toCharArray();//构建next数组数组长度为匹配串的长度这是因为next数组是和匹配串相关的int[] next new int[m1];//构造过程i2j0开始i小于等于匹配串的长度for(int i2,j0;im;i){//匹配不成功的话jnext[j]while(j0p[i]!p[j1]){j next[j];}//匹配成功的话先让jif(p[i]p[j1]){j;}//更新next[i],结束本次循环inext[i] j;}//匹配过程i1j0开始i小于等于原串长度for(int i1,j0;in;i){//匹配不成功 jnext(j)while(j0s[i]!p[j1]){jnext[j];}//匹配成功的话先让j结束本次循环后iif(s[i]p[j1]){j;}//整一段匹配成功直接返回下标if(jm){return i-m;}}return -1;}
