KMP解决字符串匹配问题

一. 什么是KMP算法

KMP算法是我们数据结构串中最难也是最重要的算法。因为KMP算法的代码很优美简洁干练，但里面包含着非常深的思维。 KMP算法就是字符串的模式匹配算法解决的问题：有一个模式字符串p，设其长度是lenp，以及另一个字符串str，设其长度lenstr，找出p在str中第一次出现的位置，显然要求lenstr>=lenp。

二. 暴力搜索解决匹配

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下

package c11KMP;

import java.util.Scanner;

import com.sun.org.apache.xerces.internal.util.SynchronizedSymbolTable;

public class StringCom {
 public static void main(String[] args) {
	
	 Scanner scanner = new Scanner(System.in);
	  System.out.println("请输入字符串：");
	String str1= scanner.nextLine();
	  System.out.println("请输入寻找的字符串：");
    String str2=scanner.nextLine();
    
	 int n=findstr(str1,str2); 
	 System.out.println("首次出现的下标："+n);
  }
	
	static int findstr(String str1,String str2) {
		char [] s1 =str1.toCharArray();
		char [] s2 =str2.toCharArray();  //把字符串转为数组
		int n1=0,n2=0;
		while(s1.length>n1) {
			//匹配s1的所有字符
			if(s1[n1]==s2[n2]) {
				n1++;
				n2++;
			  }
			else {
				n1=n1-n2+1;
				n2=0;
			}
			if(s2.length==n2) {
				//判断是否匹配成功；
				//n1 -n2
				return n1-n2+1;
			}
		}
		return -1;  //没找到时
	}
	
}

我们在暴力解决时，每次匹配不成功，都要转移到第一个去再次判断，那我们能不能利用它之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置呢？所以这就是KMP算法

三. KMP算法

这里最重要的时 寻找字符串匹配表以及在不匹配时的移动

怎么找字符串匹配表？利用前缀和后缀的值

如果给定的模式子串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：

也就是说，原模式串子串对应的各个前缀后缀的公共元素的最大长度表为（字符串匹配表）

失配时，模式子串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度

代码的实现

package c11KMP;

import java.util.Arrays;

public class KMP {

	
	
	public static void main(String[] args) {
		String str1= "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD"; // ABCDABD
		//根据部分匹配表找到值    原字符串的移位是   此位置的值-匹配表的值（传入的是已经匹配的字符串）
       int n= kmpfind(str1, str2);
		System.out.println("从0开始"+n);
		
		//int [] next =kmpNext("ABCDABD");  测试   //返回这个字符串的匹配表
		//System.out.println(Arrays.toString(next));
	}
	
	static int kmpfind(String str1,String str2) {
		int [] next=kmpNext(str2);  //返回的匹配表
		System.out.println("部分匹配表"+Arrays.toString(next));
       //循环遍历第一个字符串   i原串 j要找的字串
		for(int i=0,j=0;i<str1.length();i++) {
			//考虑不相等时  核心
			while(j>0 && str1.charAt(i)!=str2.charAt(j) )
				j=next[j-1];   //和匹配表的改变值是相同的
			if(str1.charAt(i)==str2.charAt(j)) 
				j++;  //i会做循环自动加1
            
			if(j==str2.length())
				//字串已经找完了
				return i-j+1  ;   //此时i还没移位
		    
			
		}
		
		
		return -1;
	}
	
	
	//kmp的核心函数 ，求他的匹配表
	static int [] kmpNext(String str1) {  
		//根据字符串的前缀，和后缀相等的数量 得到对应下标之前所构成的字符串他的匹配值 
				//创建匹配表  长度是字符串的值		
		int n =str1.length();
		int [] next =new int[n];
		next[0]=0;   //0位置始终为0
		for(int i=1,j=0;i<str1.length();i++) {
			//当他们不相等时  且满足j>0，  让j =j-1的字符串的匹配值  一直循环
			while(j>0 && str1.charAt(i)!=str1.charAt(j)) {
				j=next[j-1];    
			}
			 //i循环的是后缀  j循环前缀    只有在字符i j相等时  j++;
			if(str1.charAt(i)==str1.charAt(j)) {
				j++;
			  }
			//把最终得到的值放入对应的字符串下标下面
			next[i]=j;
		}
		return next;
	}
	
}

这里没有具体将思路和原理，我们只需要记住会利用，直到移动关系

如果你想了解具体原理这里是很详细的文章从头到尾彻底理解KMP（2014年8月22日版）_结构之法算法之道-CSDN博客_kmp从头到尾彻底理解KMP作者：July时间：最初写于2011年12月，2014年7月21日晚10点全部删除重写成此文，随后的半个多月不断反复改进。后收录于新书《编程之法：面试和算法心得》第4.4节中。1. 引言本KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP，但苦于一...https://blog.csdn.net/v_JULY_v/article/details/7041827