当前位置 博文首页 > Inmaturity_7的博客:KMP算法学习(Java、C语言)
学习视频:尚硅谷韩老师Java讲解数据结构与算法
学习资料:很详尽KMP算法(厉害)
package com.lxf.kmp;
public class KMP {
public static void main(String[] args) {
String str1="BBC ABCDAB ABCDABCDABDE";
String str2="ABCDABD";
System.out.println("index="+kmpSearch(str1,str2,kmpNext(str2)));
}
/**
* kmp搜索算法
* @param str1 源字符串
* @param str2 字串
* @param next 部分匹配表,是字串对应的部分匹配表
* @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
*/
public static int kmpSearch(String str1,String str2,int[] next){
//BBC ABCDAB ABCDABCDABDE
//遍历
for (int i = 0,j=0; i < str1.length(); i++) {
//需要处理str1.charAt(i)!=str2.charAt(j),去调整j的大小
//KMP算法核心点
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;
}
/**
* 获取到一个字符串(字串)的部分匹配值表
* @param dest
* @return
*/
public static int[] kmpNext(String dest){
//ABCDABD
//创建一个next数组保存部分匹配值
int[] next=new int[dest.length()];
next[0]=0;//如果字符串是长度为1
for(int i=1,j=0;i<dest.length();i++){
//当dest.charAt(i)!=dest.charAt(j)满足时,我们需要从next[j-1]获取新的j
while (j>0&&dest.charAt(i)!=dest.charAt(j)){
j=next[j-1];
}
//当dest.charAt(i)==dest.charAt(j)满足时,部分匹配值就+1
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
next[i]=j;
}
return next;
}
}
KMP算法之java实现–next[]数组
#include<stdio.h>
typedef struct String{
char* ch;
int length;
}String;
//求next数组
void get_next(String T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;
++j;
next[i]=j;
}else{
j=next[j];//否则令j=next[j],循环继续
}
}
}
///nextval数组(next数组的优化)
void get_nextval(String T,int nextval[]){
int i=1,j=0;
nextval[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;
++j;
if(T.ch[i]!=T.ch[j]){
nextval[i]=j;
}else{
nextval[i]=nextval[j];
}
}else{
j=nextval[j];
}
}
}
//KMP算法
int Index_KMP(String S,String T,int next[]){
int i=1,j=1;
while(i<=S.length&&j<=T.length){
if(j==0||S.ch[i]==T.ch[j]){
++i;++j;//继续比较后继字符
}else{
j=next[j];//模式串向右移动
}
}
if(j>T.length)
return i-T.length;//匹配成功
}
int main(){
}
cs