KMP算法的简单理解

「爱情、让人受尽委屈。」 2023-07-07 08:17 231阅读 0赞

## 引入 ##

对于串的匹配，较为简单的有BF算法，但这种方法的可用性却较差。因为在每次不匹配的时候，主串（m位）和子串（n位）都会回溯,有一种最坏的情况就是，主串每前进一位，都在n次匹配后失败然后回溯，如：  
主串：aaaaaaaaaaaaaaaaaaaaab  
子串：aab  
这样会导致BF算法的时间复杂度大大提升：  
T = O（（m-n）\*n））≈ O（m\*n） 由于 m串长度 >> n串长度 一般忽略  
然而，在实际应用中，时间带给用户的体验是最为重要的，一般都是不惜增加空间复杂度而来提高时间复杂度。

这时KMP算法的出现，大大优化了BF算法的这一缺陷。

## KMP ##

KMP算法是以D.E.Knuth、J.H.Morris和V.R.Pratt共同命名的算法，是他们3人在同一时期异途同归的结果，故简称KMP算法。  
实质：是消除了主串的回溯，并且使得子串的指针是跳跃性的定位，大大提升了算法的效率。

**想法**：在BF算法进行的过程中，若子串匹配到最后一位时发现不匹配，子串和主串同时回溯。这会使得无用功变了许多。但是，当子串和主串已经匹配了许多位时，意味着主串已匹配的部分已经被我们所知（即子串的部分），那何不对子串进行预先处理，在进行匹配时使得主串已匹配过的部分不再是无效的，如：  
主串：aabaabaac  
子串：aabaac  
当主串匹配到五位匹配不成功时，对子串进行回溯：由于子串中该数据之前有相同的前缀和后缀，即子串本身的开头部分和中间部分能够进行匹配，而此时在主串中已匹配的数据部分是和子串一样的，即子串的开头部分仍能匹配到主串的部分数据。

经过这样的推导，使得这一想法的建立过程逐渐明确，也就是我们的KMP算法。

## next数组 ##

在进行匹配的过程中，主串是一直进行遍历，而子串需要进行回溯。问题是：子串是怎么回溯的？  
这就需要我们对子串的内容进行分析得到next数组作为子串回溯的依据，当然这也是KMP算法中最重要和最难的一点。

**next实质**：子串想要回溯，该回溯到哪儿。经过之前的想法，我们可以发现当子串的某位数据前出现了相同的前缀和后缀时，也意味着此时子串的开头部分和主串是能够匹配的。所以next数组的实质就是找到每个数据之前的相同前缀和后缀长度，在匹配过程中能够通过长度定位到相匹配的地方。

**建立：此处我以串的格式进行建立：首位存放长度，之后存储数据，数组名a\[\]  
①对于a\[1\]来说，匹配长度为0，则next\[1\] = 0（此处若数组首位有值，next\[0\] = -1)  
②定义一个 i 来遍历数组，定义 j 来进行匹配测试同时也记录匹配长度。  
③i 从2开始向后遍历  
④ 对a\[i\] 和 a\[j+1\] 进行判断（判断已匹配的下一位，此时应该会理解初始值0和-1的原因）  
⑤若不相等且未回溯到子串首位，对于 j 进行回溯（因为 i 之前的next数组已经建立，这里相当于KMP算法中的子串指针进行跳跃）  
⑥若相等，j++（匹配长度加一）  
⑦next\[i\] = j （根据匹配结果对于next数组进行赋值）**

如：aadaac  
c处next数组为2，当主串匹配到（c）时匹配失败，则可回溯到 a\[2\] 对其下一位（d）进行匹配

## 匹配过程 ##

此时我们已经求得了next数组，在匹配的过程中可以不像BF算法中两者都进行回溯，在处理过程中和求next数组的方法类似（一个是主串和子串，一个是子串和子串）：当匹配失败时，对next数组循环回溯，直至找到相同的部分或者  
回溯到子串首部。

## 实际案例 ##

此处我写了一个案例进行测试：将文件中的数据进行导入以串的形式存储，输入子串进行匹配  
①数据导入函数

//数据节点
    class strandNode{
     	private String data; 
    	private strandNode nextNode;
    	
    	//get、set方法
     }
     /**
         * 从文件中读取数据，构建主串（链式存储）
         * @param str    文件名
         * @return   头指针（未存储数据）
         */
     public strandNode getMainStrand(String str) {
     	 //设立头指针,不存储数据
     	strandNode headNode = new strandNode();
      	//防止未读入数据，指针越界
      	headNode.setNextNode(null);
      	//设立移动指针，建立链式结构
      	strandNode moveNode = headNode;
      	BufferedReader bReader = null;
      	try {
       		bReader = new BufferedReader(
               								new FileReader(new File(str)));
      		//读取数据并添加到链表中
       		String data;
       		while((data = bReader.readLine()) != null) {
        			strandNode midNode = new strandNode();
        			midNode.setData(data);
        			moveNode.setNextNode(midNode);
        			moveNode = midNode;
       		}
      		 //末尾置空
       		moveNode.setNextNode(null);      
    	  } catch (Exception e) {
       	  	e.printStackTrace();
     	  }finally {
       			try {
        				if(bReader != null) {
         					bReader.close();
        				}
        
       			} catch (IOException e) {
        				e.printStackTrace();
       			}
      	}
     	return headNode;
     }

②根据子串求出next数组

/**
      * 根据子串计算出next数组
      * @param son 子串（首位为空）
      * @return    next数组
      */
     public int[] analyNext(char son[]) {
      	//next存储本位置（包含本位置）之前的前后缀最长匹配长度（以0开始），若以-1开始则是存放长度-1
     	//根据子串的长度初始化next数组
      	int[] next = new int[son.length];
      	//设置初始值，由于第一位未存放数据，则置0
     	 next[1] = 0;
      	//设置一个主指针i，用于更新next数组
      	//设置一个匹配指针j，用于判断匹配,并记录长度
      	int j = 0;
      	for(int i= 2; i< son.length; i++) {
       		//当两者不匹配时，需向前回溯
       		//此时，对于i之前的next数组已经成立，则只需通过next数组找到上一个匹配的位置
       		while(son[i] != son[j+1] && j != 0) {
        		j = next[j];
      	}
       	//若两者相等，则匹配长度加一
       	if(son[i] == son[j+1]) {        
        		j++;
      	}
        	next[i] = j;
      	}
      	return next; 
     }

③匹配过程

/**
      * 进行匹配算法
      * @param headNode   主串头指针
      * @param son        子串
      * @param next       根据子串建立的next数组
      * @return   子串在主串中的位置（未找到返回零）
      */
     public String strandMatched(strandNode headNode, char son[], int next[]) {
      	//将主串转换为char数组进行匹配
      	StringBuilder result = new StringBuilder();
      	StringBuilder sBuilder = new StringBuilder(" ");   //头部置空
      	strandNode moveNode = headNode.getNextNode();
      	while(moveNode != null) {
      		sBuilder.append(moveNode.getData());
       		moveNode = moveNode.getNextNode();
      	}
      	char mainStrand[] = sBuilder.toString().toCharArray();
     	//求取串长，提高每次判断所用效率
      	int mainLength = mainStrand.length;
      	int sonLength = son.length;
      	//进行匹配
      	int j = 0;   //子串的游标
      	for(int i=1; i<mainLength; i++) {
       	//若匹配不成功，子串回溯，直至匹配成功或回溯至首位
       		while(mainStrand[i] != son[j+1] && j != 0 ) {
        			j = next[j];   
       		} 
       		//匹配成功，继续遍历 
       		if(mainStrand[i] == son[j+1]) {    
        			//匹配到子串末尾,结束
       			if(j+1 == sonLength-1) {  
         				//对匹配结果进行存储,子串重置
         				result.append(i-j+"%");   
        			 	j = 0;
    	    		}
        			j++;    
       		}
      	}    
      	return result.toString();  
     }

④主函数

public static void main(String[] args) {
      	Scanner scan = new Scanner(System.in);
      	System.out.print("请输入要匹配的子串：");
      	String son = scan.nextLine();
      	Kmp kmp = new Kmp();
      	//将文件中的内容进行加载,得到头指针
      	strandNode headNode = kmp.getMainStrand("TestData/kmpinput.txt");
      	//求出next数组
      	char sonStrand[] = (" "+son).toCharArray();
      	int next[] = kmp.analyNext(sonStrand);
      	//进行匹配
      	String result = kmp.strandMatched(headNode, sonStrand, next);
     	if(result == null) {
       		System.out.println("匹配失败！！！");
      	}else {
       		String str[] = result.split("%");
       		System.out.println("匹配成功！！！共匹配到："+str.length+"处");
       		for(int i=0; i< str.length; i++)
       		System.out.println("子串第"+(i+1)+"次在主串的第"+str[i]+"位出现");
      	}  
     }

## 结果验证 ##

主串文件（幻听全文）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]  
对于匹配位置的验证：  
![在这里插入图片描述][20200221223007803.png]  
（“ ”并未读取到串中）首段开头18位

对于多次匹配的测试：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200221222944941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[20200221223007803.png]: https://img-blog.csdnimg.cn/20200221223007803.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200221223158870.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70