<commit_before>---
layout: post
title: KMP算法
category: 算法
description: KMP算法
tags: ["C++","算法"]
---

Coursera上对KMP讲的真是...节奏奇怪，还讲不清楚。

k = match到的最大长度  
j = P string 的长度-1  
k = -1 when j = 0;  
特征向量N[j] = k;  

### 求特征向量的算法框架：未优化版(课ppt上的原代码)

```
    int findNext(string P){
    int m = P.length();
    assert( m > 0 );
    
    int *next = new int[m];
    assert( next != 0);
    next[0] = -1; 
    
    int j = 0,k = -1;
    while(j < m-1){
        while (k >= 0 && P[k] != P[j])     //不知为何它要用while，其实用if就行了
            k = next[k];                   //循环结束，不写括号容易看错; 按它的逻辑这里应该k=-1；这里完全就是错的
            j++; k++; next[j] = k;
    }
        return next;
    }
```
    
### 求特征向量的算法框架：未优化版(修改版)
其实思想相当简单，就是遍历字符串，拿第一个字符P[0]和别的字符一个一个对比，如果相同，k++，然后拿第二个字符P[1]和下一个字符对比，以此类推。这样我们拿的字符的位置又可以由k表示，即P[k]。值得注意的一点是我们假设字符长度大于二，因为当字符长度小于等于2的时候不需要KMP。

```
    //特征向量：最长的首尾配串值k
    int *findNext(string P){
		int m = P.length();
		assert( m > 2 );
    
		int *next = new int[m];
		assert( next != 0);
		next[0] = -1;
		next[1] =  0; 
    
		int k = 0;
		for(int j=2;j
		{
			if(P[k]==P[j-1]) k++;
			else             k=0;
			next[j]=k;
		}
    
		return next;
    }
```
   
### 求特征向量的算法框架：优化版(ppt上的原代码)

```
    int *findNext(string P) {
		int j = 0; 
		int k = -1; 
		int m = P.length();       // m为字符串P的长度
		assert(m > 0);            // 若m＝0，退出
		int *next = new int[m];   // 动态存储区开辟整数数组
		assert(next != 0);        // 若开辟存储区域失败，退出
		next[0] = -1;
		while (j < m) {           // 计算i=1..m-1的next值
			while (k >= 0 && P[j] != P[k])   // 求最大首尾子串
			k = next[k];
			j++;
			k++;
			if (j == m) break;
			if (P[j] == P[k] )
				next[j] = next[k]; //  P[i]和P[k]相等，优化
			else next[j] = k; // 不需要优化，就是位置i的首尾子串长度
        }
        return next;
    }
```
    
### 在计算好特征向量N[j]之后，匹配算法很简单就能实现：

```
    int KMPStrMatching(string T, string P,  int *N) {
        int i = 0; // 模式的下标变量
        int j = 0; // 目标的下标变量
        int pLen = P.length();             // 模式的长度
        int tLen = T.length(); // 目标的长度
    
        if (tLen < pLen)     // 如果目标比模式短，匹配无法成功
            return (-1);
    
        while ( i < pLen  &&  j < tLen)  {   // 反复比较对应字符来开始匹配
            if ( i == -1  ||  T[j] == P[i]) 
			i++,  j++;
			//向后移动位数 = 已匹配的字符数N[i] - 对应的部分匹配值
			//等价于重新从N[i]表示的那个数开始计数
			else i = N[i];
        }
    
        if ( i >= pLen)  return (j - pLen);
        else             return (-1);
    }
```    


reference：  
1. http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html  
2. https://class.coursera.org/dsalgo-001/lecture/31  

P.S.
1.比KMP更好的算法：Boyer–Moore算法  
2.KMP实际上是AC自动机的特殊情况  
<commit_msg>Update 2014-06-20-KMP.md<commit_after>---
layout: post
title: KMP算法(Knuth–Morris–Pratt algorithm)
category: 算法
description: KMP算法
tags: ["C++","算法"]
---

Coursera上对KMP讲的真是...节奏奇怪，还讲不清楚。

k = match到的最大长度  
j = P string 的长度-1  
k = -1 when j = 0;  
特征向量N[j] = k;  

### 求特征向量的算法框架：未优化版(课ppt上的原代码)

```
    int findNext(string P){
    int m = P.length();
    assert( m > 0 );
    
    int *next = new int[m];
    assert( next != 0);
    next[0] = -1; 
    
    int j = 0,k = -1;
    while(j < m-1){
        while (k >= 0 && P[k] != P[j])     //不知为何它要用while，其实用if就行了
            k = next[k];                   //循环结束，不写括号容易看错; 按它的逻辑这里应该k=-1；这里完全就是错的
            j++; k++; next[j] = k;
    }
        return next;
    }
```
    
### 求特征向量的算法框架：未优化版(修改版)
其实思想相当简单，就是遍历字符串，拿第一个字符P[0]和别的字符一个一个对比，如果相同，k++，然后拿第二个字符P[1]和下一个字符对比，以此类推。这样我们拿的字符的位置又可以由k表示，即P[k]。值得注意的一点是我们假设字符长度大于二，因为当字符长度小于等于2的时候不需要KMP。

```
    //特征向量：最长的首尾配串值k
    int *findNext(string P){
		int m = P.length();
		assert( m > 2 );
    
		int *next = new int[m];
		assert( next != 0);
		next[0] = -1;
		next[1] =  0; 
    
		int k = 0;
		for(int j=2;j
		{
			if(P[k]==P[j-1]) k++;
			else             k=0;
			next[j]=k;
		}
    
		return next;
    }
```
   
### 求特征向量的算法框架：优化版(ppt上的原代码)

```
    int *findNext(string P) {
		int j = 0; 
		int k = -1; 
		int m = P.length();       // m为字符串P的长度
		assert(m > 0);            // 若m＝0，退出
		int *next = new int[m];   // 动态存储区开辟整数数组
		assert(next != 0);        // 若开辟存储区域失败，退出
		next[0] = -1;
		while (j < m) {           // 计算i=1..m-1的next值
			while (k >= 0 && P[j] != P[k])   // 求最大首尾子串
			k = next[k];
			j++;
			k++;
			if (j == m) break;
			if (P[j] == P[k] )
				next[j] = next[k]; //  P[i]和P[k]相等，优化
			else next[j] = k; // 不需要优化，就是位置i的首尾子串长度
        }
        return next;
    }
```
    
### 在计算好特征向量N[j]之后，匹配算法很简单就能实现：

```
    int KMPStrMatching(string T, string P,  int *N) {
        int i = 0; // 模式的下标变量
        int j = 0; // 目标的下标变量
        int pLen = P.length();             // 模式的长度
        int tLen = T.length(); // 目标的长度
    
        if (tLen < pLen)     // 如果目标比模式短，匹配无法成功
            return (-1);
    
        while ( i < pLen  &&  j < tLen)  {   // 反复比较对应字符来开始匹配
            if ( i == -1  ||  T[j] == P[i]) 
			i++,  j++;
			//向后移动位数 = 已匹配的字符数N[i] - 对应的部分匹配值
			//等价于重新从N[i]表示的那个数开始计数
			else i = N[i];
        }
    
        if ( i >= pLen)  return (j - pLen);
        else             return (-1);
    }
```    


reference：  
1. http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html  
2. https://class.coursera.org/dsalgo-001/lecture/31  

P.S.
1.比KMP更好的算法：Boyer–Moore算法  
2.KMP实际上是AC自动机的特殊情况  

{'fraction_non_alphanumeric': 0.18648286425426, 'fraction_numerical': 0.022592379858318974, 'mean_word_length': 1.8040794417606012, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 15, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5876299', 'n_tokens_mistral': 3036, 'n_tokens_neox': 3065, 'n_words': 452}