1.KMP算法

1.1 简介

研究的是子串（必须连续）。

int getIndexOf(String str1,String str2);

用的就是KMP算法，不在时返回-1；在时返回在原串中的位置。

时间复杂度是，最起码得遍历完原串。

最坏情况，时间复杂度为.

KMP算法：让前面配过的元素指导后面的匹配，这样就可以加速匹配。

1.2 最长前缀和最长后缀之间的匹配长度

一个字符之前的那个字符串的最长前缀和最长后缀之间的匹配长度（前缀不能包含最后一个字符，后缀也不能包含最前的一个字符）。

1.2.1 举例1

上题中：

• 长度取1：a≠c
• 长度取2：ab≠bc
• 长度取3：abc=abc
• 长度取4：abca≠cabc
• 长度取5：abcab不等于bcabc
• 长度只能取到5

所以答案为3.

1.2.2 举例2

此题中，答案是4

1.2.3 引到next数组

对字符串中的每一位进行计算，得到一个next数组：

1.3 KMP过程

下面，开始用str2的这个next数组进行KMP的过程解释。

假设现在从str1的i位置开始h和str2的0位置开始匹配：

一路都匹配，直到x和y不匹配。

1.3.1 暴力方法

从str1的i+1位置开始，继续和str2的0位置开始匹配。

1.3.2 改进方法

依据y位置的next值，进行加速处理。

假设Y位置的最长前缀和最长后缀的长度如图所示：

将str2中的后缀对应到str1中对应的位置，如下图：

假设str1中相对应的位置起始为j位置，那么接下来就是str1的j位置和str2的0位置开始往后匹配，如下图;

由于str2中前缀标出的部分和后缀中标出的部分是相匹配的，所以str2中前缀的部分和str1中从j位置开始的等长部分也匹配。所以，现在实际上开始匹配的位置是str1中的j位置和str2中的k位置，即比较x和z是否匹配。如图：

1.3.3 举例1

1.3.3 推两次举例

第一次：i是str1中的图中开始的a的位置；j是第一次推之后str1中和str2中0位置比较的位置；

第二次：i是第一次的j，j是第二次推之后，str1中和str2中0位置比较的位置。

第一次看F的next，决定str2推的位置，D和a没匹配上；

此时看a的next决定第二次往后退的位置，2个。比较D和k。没匹配上；

k位置的next为0，所以下一步就是D之后的字符和str2的0位置元素开始匹配。

1.3.4 推的过程的实质

第一次匹配完之后，甲在t位置，乙在F位置，然后甲不动，乙跳到str2中的5位置（即，乙跳到str2中的next[F]的位置），继续和甲指向的元素t进行匹配。

1.3.5 具体匹配过程

1. 甲指向的字符和乙指向的字符相等：甲++；乙++；
2. 若不相等：
   1. 乙指向字符对应的next为-1，则说明是str2的起始位置，甲++（即，甲指向的str1中的字符和str2中0位置的字符都不匹配，那就是str1后一个字符继续和str2中0位置的字符比较）；
   2. 否则，乙跳到str2中的next[乙]的位置。
3. 若循环完之后，乙位置超过了str2，则说明匹配成功，返回甲-乙（目前匹配到的位置-乙=str2在str1中的位置）；否则返回-1，即不存在。

1.4 next数组的求解

0位置为-1，1位置为0，2位置（若0位置和1位置的字符相等则为1，否则为0）。

其他位置：数学归纳法

目前要求i位置的next值。已知i-1位置的next值为4。则，若前缀串的后一个字符x=b（i-1位置的字符），则i位置的next值为4+1=5。

如果不等：

则看前缀后面的字符x的next值，划分出它的前缀和后缀，然后看x的最长前缀之后的字符和b（i-1位置的字符）是否相等，相等则i位置的next值为x的next值+1，否则继续分。一直到没得分，则i位置的next值才为0；

1.4.1 举例1

1.4.2 举例2

将1.4.1中的i-1位置换为a：

1.2 代码实现

package Classics;public class KMP {public static void main(String[] args) {String str = "abcabcababaccc";String match = "ababa";System.out.println(getIndexOf(str, match));}public static int getIndexOf(String str1,String str2) {if(str1==null||str2==null)return -1;int i1=0;int i2=0;int[] next=getNextArray(str2);char[] chs1=str1.toCharArray();char[] chs2=str2.toCharArray();while(i1-1){i2=next[i2];//回退}else {//i2在str2的0位置，则需要i1的下一个位置来和str2的0位置（i2位置）匹配i1++;}}return i2==str2.length()?i1-i2:-1;}public static int[] getNextArray(String str2) {if(str2.length()==1)return new int[] {-1};char[] chs=str2.toCharArray();int[] next=new int[chs.length];next[0]=-1;next[1]=0;int i=2;int cn=0;while(i0){cn=next[cn];}else {next[i++]=0;}}return next;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！