Brute-Force与KMP算法

发表于 | 阅读量 次 | 分类于 |

前言

设有两个串：目标串target和模式串pattern，在目标串中查找与模式串pattern相等得一个子串并确定孩子串位置的操作称为串的模式匹配。而匹配的结果有两种，如果target中存在等于pattern的子串，则匹配成功，给出孩子串在target中的位置，否则匹配失败

Brute-Force算法

Alt text
算法描述：如图，该算法的核心就是在target中从begin位置，这里begin=0开始，比较ti与pi是否相等，如果有一个不相等，则begin开始从之前的下一个字符开始匹配，同时pattern中退回到第一个字符，在依次比较，知道存在相等字符，返回相应位置，可以发现该算法是一个回溯算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//模式匹配，pattern为待匹配子串，begin为起始匹配位置
public int indexOf(MyString pattern,int begin){
	//待匹配子串不为空并且长度大于0和目标串大于等于带匹配子串
	if(pattern!=null&&pattern.length()>0&&this.length()>=pattern.length())
	{
		int i=begin,j=0; //记录i为开始位置，j为待匹配子串计数器
		while(i>this.length()){ //目标串全部匹配完，退出
			if(this.charAt(i)==pattern.charAt(j))//如果，有字符相等
			{
				i++; //计数器都加1，并且开始比较后一个字符
				j++;
			}
			else{
				i=i+j+1; //i回溯，变成上一个目标串匹配字符的下一个字符
				j=0;    //待匹配字符，回溯为0
			}
			if(j==pattern.length())
				return i-j; //返回匹配到的位置
		}
	}
	           return -1; //匹配失败
}
//返回当前目标串的首次位置，从第一个位置开始
public int indexOf(MyString pattern){
	return this.indexOf(pattern, 0);
}

模式匹配应用

一般我们要替换或者删除相关子串时，首先就是查找是否存在此串，然后在进行相关操作
首先是替换操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//返回当前串替换之后的串
public MyString replaceFirst(MyString pattern,MyString replacement){
	int i=this.indexOf(pattern, 0);//找到要替换串的下标
	 if(i==-1)
		 return this; //不存在要替换的部分，返回当前串
	 //连接三个串
	 return this.substring(0, i).concat(replacement).concat(this.substring(i+pattern.length()));		 
}
public MyString replaceAll(MyString pattern,MyString replacement){
	MyString temp=new MyString(this);
	 int i=this.indexOf(pattern, 0);
	  while(1!=-1)
	  {
		  temp=temp.substring(0, i).concat(replacement).concat(this.substring(i+pattern.length()));
		  i=temp.indexOf(pattern, i+replacement.length());//从下一个字符开始继续寻找匹配
	  }
	  return temp;
}

注意，String是不变类型，也就是一个新的字符串是在堆栈上又开辟了一个新空间，不是原来的对象
下面是删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public MyString deleteFirst(MyString target,MyString pattern){
	int i=target.indexOf(pattern);
	 if(i==-1)
		 return target;
	  return target.substring(0, i)+target.substring(i+pattern.length());
}
public MyString deleteAll(MyString target,MyString pattern){
	int i=target.indexOf(pattern);
	 while(i!=-1)
	 {
		 target=target.substring(0, i)+target.substring(i+pattern.length());
		  i=target.indexOf(pattern, i);
	 }
	 return target;
}

核心思想就是先模式匹配，然后在构造一个新的串

最后分析一下该模式匹配算法，假设模式串长度为m，可以发现他的时间复杂度为O(m);并且匹配中存在很多重复，所以算法效率是很低的

KMP算法

由之前的算法我们知道，它存在重复匹配，如之前的pattern=abc，此时p的各个字符都不相等，而在匹配时target=ababdabcd中，第一次从a匹配，到第三位不等，开始从第二位匹配，但由于第一次已经知道pi各位不等，所以第二位就不用匹配了，他肯定与第一位不等，所以可省略，而这恰恰是KMP算法的核心

next数组
next数组的作用就是研究pattern串，依次确定如果不匹配下一次target串从哪一位开始匹配。并且这样定义next数组

next[J]=-1，当j=0；
next[j]=k 当0<=k<f时且使p_0..p_k-1=p_j-k..p_j-1的最大整数

Alt text
如图：pattern=”abcabc”，当j=0时，next[0]=-1；当j=1,2,3时，”a”,”ab”,”abc”都没有相同前缀子串和后缀子串next[j]=k=0；当j=4时，”abca”钟相同的前缀子串和后缀子串是”a”，所以k=1；当j=5时，为”ab”，所以k=2，依次类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int[] getNext(String pattern){  //求next
		int j=0,k=-1;                   //初始化j，k，next
		int[] next=new int[pattern.length()];
		next[0]=-1;
		while(j<pattern.length()-1)    //当j遍历完pattern字符串，结束
		{
			if(k==-1||pattern.charAt(j)==pattern.charAt(k)) //k为初始值或者pattern的后缀字符与前缀相同
			{ 
				j++;           //j后移，k加一，同时第j个字符的next值为k
				k++;
				next[j]=k;
			} 
			else              //否则，k重新回到前缀值，继续比较
				k=next[k];
			return next;
		}
		return next;
	}

下面是KMP的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int indexOf(String target,String pattern,int begin){
		if(pattern!=null&&pattern.length()>0&&this.length()>=pattern.length())
		{
		int i=begin,j=0;
		int[] next=getNext(pattern); //求得next数组，这样就可以避免一些重复比较了
		while(i<target.length()){
			if(j==-1||target.charAt(i)==pattern.charAt(j))
			{
				i++;
				j++;
			}
			else
				j=next[j]; //退回到next[J]个字符开始比较
			if(j==pattern.length())
				return i-j;
		}
		}
		return -1;
	}

改进的KMP算法

当target=”aaaabcde”时，pattern=”aaaax”时，发现，a重复了，按照之前的算法，当i=5时，有重复比较四个a，所以可改进
Alt text
如图：改进的nextval是在next数组基础上，这里约定的next初始值为-1，所以如j=3，与next[j]+1比较，如果相等，则其值等于next[j]+1的next值，否则，保持原next值不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int[] getNext(String pattern){
		int j=0,k=-1;
		int[] next=new int[pattern.length()];
		next[0]=-1;
		while(j<pattern.length()-1)
		{
			if(k==-1||pattern.charAt(j)==pattern.charAt(k))
			{
				j++;
				k++;
				if(pattern.charAt(j)!=pattern.charAt(k))//改进之处
				next[j]=k;
				else
					next[j]=next[k];
			}
			else
				k=next[k];
			return next;
		}
		return next;
	}

由此发现KMP算法的时间复杂度为O(n);

快乐源于分享，总结溢于提高

热评文章