字符串的模式匹配（Java实现）

　　字符串的模式匹配

字串的定位操作通常称做模式匹配，是各种串处理系统中最重要的操作之一。本文主要介绍两种常用的实现算法：

　　1、暴力匹配

　　2、KMP算法

 

1.暴力匹配

　　时间复杂度为O(n*m)；n为主串长度，m为模式串长度

　　算法的基本思想：

　　　　　　从主串的起始位置（或指定位置）开始与模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符再重新和模式串的字符比较。依次类推，直到模式串成功匹配，返回主串中第一次出现模式串字符的位置，或者模式串匹配不成功，这里约定返回-1；

　

//伪代码 int bruteForceStringMatch(String source, String pattern) {i = 0; j = 0;while(i < slen && j < plen){if(s[i] == p[j])++i; ++j;elsei = i - (j -1); //回溯上次匹配起始位置的后一位j = 0;}if(j == plen) return i - j; //匹配成功elsereturn -1; //匹配失败 }

实现代码：

1 public static int bruteForceStringMatch(String source, String pattern) 2 { 3 int slen = source.length(); 4 int plen = pattern.length(); 5 char[] s = source.toCharArray(); 6 char[] p = pattern.toCharArray(); 7 int i = 0; 8 int j = 0; 9 10 if(slen < plen) 11 return -1; //如果主串长度小于模式串，直接返回-1，匹配失败 12 else 13 { 14 while(i < slen && j < plen) 15 { 16 if(s[i] == p[j]) //如果i,j位置上的字符匹配成功就继续向后匹配 17 { 18 ++i; 19 ++j; 20 } 21 else 22 { 23 i = i - (j -1); //i回溯到主串上一次开始匹配下一个位置的地方 24 j = 0; //j重置，模式串从开始再次进行匹配 25 } 26 } 27 if(j == plen) //匹配成功 28 return i - j; 29 else 30 return -1; //匹配失败 31 } 32 } View Code

 

2.KMP算法

　　KMP算法是D.E.Knuth、V.R.Pratt和J.H.Morris同时发现，所以命名为KMP算法。

　　此算法可以在O(n+m)的时间数量级上完成串的模式匹配。

　　主要就是改进了暴力匹配中i回溯的操作，KMP算法中当一趟匹配过程中出现字符比较不等时，不直接回溯i，而是利用已经得到的“部分匹配”的结果将模式串向右移动（j-next[k]）的距离。稍后我们将详细解释next[k]的计算过程。

//伪代码 int kmpStringMatch(String source, String pattern) {i = 0；j = 1;while(i < slen && j < plen){if(j == 0 || s[i] == p[j]) ++i; ++j;elsej = next[j]; }if(j == plen)return i - j;elsereturn -1; }

实现代码：

1 public static int kmpStringMatch(String source, String pattern) 2 { 3 int i = 0; 4 int j = 0; 5 char[] s = source.toCharArray(); 6 char[] p = pattern.toCharArray(); 7 int slen = s.length; 8 int plen = p.length; 9 int[] next = getNext(p); 10 while(i < slen && j < plen) 11 { 12 if(j == -1 || s[i] == p[j]) 13 { 14 ++i; 15 ++j; 16 } 17 else 18 { 19 //如果j != -1且当前字符匹配失败，则令i不变， 20 //j = next[j],即让pattern模式串右移j - next[j]个单位 21 j = next[j]; 22 } 23 } 24 if(j == plen) 25 return i - j; 26 else 27 return -1; 28 } View Code

 

那么问题来了，next[k]是怎么计算出来的呢？

关于next[k]数组的计算引出的两种办法，一种是递归，一种对递归优化，第一种对应的就是KMP算法，第二种就是优化的KMP算法。

next函数值仅取决于模式串本身而和主串无关。

有很多讲next函数值计算办法的资料，在此我想用一种直观的比较容易理解的办法来表达。

举个栗子：现在有一个模式串abab

模式串的各个字串	前缀	后缀	最大公共元素长度
a	null	null	0
ab	a	b	0
aba	a,ab	a,ba	1
abab	a,ab,aba	b,ab,bab	2

 

 

 

 

next函数值的实现：

private static int[] getNext(char[] p){/*** 已知next[j] = k, 利用递归的思想求出next[j+1]的值* 1.如果p[j] = p[k]，则next[j+1] = next[k] + 1;* 2.如果p[j] != p[k],则令k = next[k],如果此时p[j] == p[k],则next[j+1] = k+1* 如果不相等，则继续递归前缀索引，令k=next[k],继续判断，直至k=-1(即k=next[0])或者p[j]=p[k]为止*/int plen = p.length;int[] next = new int[plen];int k = -1;int j = 0;next[0] = -1; //这里采用-1做标识while(j < plen -1){if(k == -1 || p[j] == p[k]){++k;++j;next[j] = k;}else{k = next[k];}}return next;} View Code

国际惯例贴上源代码：

import java.util.Scanner;public class PatternString {public static int bruteForceStringMatch(String source, String pattern){int slen = source.length();int plen = pattern.length();char[] s = source.toCharArray();char[] p = pattern.toCharArray();int i = 0;int j = 0;if(slen < plen)return -1; //如果主串长度小于模式串，直接返回-1，匹配失败else{while(i < slen && j < plen) {if(s[i] == p[j]) //如果i,j位置上的字符匹配成功就继续向后匹配 {++i;++j;}else{i = i - (j -1); //i回溯到主串上一次开始匹配下一个位置的地方j = 0; //j重置，模式串从开始再次进行匹配 }}if(j == plen) //匹配成功return i - j;elsereturn -1; //匹配失败 }}public static int kmpStringMatch(String source, String pattern){int i = 0;int j = 0;char[] s = source.toCharArray();char[] p = pattern.toCharArray();int slen = s.length;int plen = p.length;int[] next = getNext(p);while(i < slen && j < plen){if(j == -1 || s[i] == p[j]){++i;++j;}else{//如果j != -1且当前字符匹配失败，则令i不变，//j = next[j],即让pattern模式串右移j - next[j]个单位j = next[j];}}if(j == plen)return i - j;elsereturn -1;}private static int[] getNext(char[] p){/*** 已知next[j] = k, 利用递归的思想求出next[j+1]的值* 1.如果p[j] = p[k]，则next[j+1] = next[k] + 1;* 2.如果p[j] != p[k],则令k = next[k],如果此时p[j] == p[k],则next[j+1] = k+1* 如果不相等，则继续递归前缀索引，令k=next[k],继续判断，直至k=-1(即k=next[0])或者p[j]=p[k]为止*/int plen = p.length;int[] next = new int[plen];int k = -1;int j = 0;next[0] = -1; //这里采用-1做标识while(j < plen -1){if(k == -1 || p[j] == p[k]){++k;++j;next[j] = k;}else{k = next[k];}}System.out.println("next函数值：");for(int ii = 0;ii<next.length;ii++){System.out.print(next[ii]+ " ");}System.out.println();return next;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String a = sc.nextLine();String b = sc.nextLine();System.out.println(bruteForceStringMatch(a, b));System.out.println(kmpStringMatch(a, b));}} View Code

转载于:https://www.cnblogs.com/jiaohanhan/p/6654874.html

总结

以上是生活随笔为你收集整理的字符串的模式匹配（Java实现）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。