又见 “KMP”

- 日理万妓 2022-03-20 01:23 278阅读 0赞

同 [http://blog.csdn.net/shanshanpt/article/details/8679459][http_blog.csdn.net_shanshanpt_article_details_8679459] ，都是回忆版

>: KMP的一些概念介绍就不用了，网上到处都是，此处只是为了整理，仅此而已

>: 网上看到的文章都是从 “ next ”数组和i，j指针的移动来讲的，这里也一样，不过不同的是，想说的更清晰一点！

>: 传统的BF算法与KMP有什么区别呢？

BF： 原串： B A B A  B ...

子串：  B A B A D     此时匹配不上了，那么它又会从下一个字符开始：   原串： A B A B ....

\----------------------------------------------------------------------------------------------------------子串：     A B A D -----------------------------------------------------------------------------------------------------

然后再接着找，那么这样我们前期的一些匹配就浪费了，而KMP就是尽最大的可能去利用已经做过的工作！

KMP： 原串： B A B A  B A D A A ....

子串： B A B A  D .

不好，发现到不匹配的，怎么办呢，此时KMP不想BF那么傻，从头再开始，而是-------> 对于前面的已经字符串啊，它总是想找到一个分界( 其实就是一个长度m )，能够使得什么呢，能使得最前面的m长度字串( 从前面往后数m个char )和最后面的m个长度字串( 从后往前数m个char，注意此处说的是前面已经匹配成功的一部分哦~^\_^ )是相等的！那么变成什么呢？

原串：B A B A B A D A A ....

子串：       B A B A D     那么我们可以看到 下面的连个B A  其实就是前面已经匹配过的字串相等的情况( 子不过此处有点特殊，下面再看个实例 )

因为我们知道之前是字串中是的D不匹配，当我们找到头部m长度字串和尾部m长度字串相等的时候，那么此时头部m长度

移动到原来尾部m长度处，那么与原串中的相应的m长度必然是匹配的！这就是Kmp不同于BF的关键之处！

再看一个实例：

原串： B A C B A  B A D A A ....

子串： B A C B A  D .

KMP处理后变成：

原串：B A C B A B A D A A ....

子串：           B A C B A D       红色 B 和 D是之前不匹配处，绿色的三个 B A 就是上面KMP处理的结果！

>:  讲了这么多，大家都可以认为是废话哦，呵呵，下面就是重要的next数组求解：使用的是递推法！

>: 我们一般定义next\[0\] = -1，假设 next\[j\] = k,  即 M\[ 0...k - 1 \] == M\[ j - k... j - 1 \];

>: 然后接着往下扫描，若M\[j\] == M\[k\]，则有M\[ 0..k \] == M\[ j - k , j \]，很显然，next\[ j + 1 \] = next\[ j \]，而next\[j\] == k,那么有next\[ j + 1 \] = k + 1;

>:                           若M\[j\] != M\[k\]， 匹配失败的时候，k = next\[k\] ( 书上是这么写的，可是为什么呢？ ) 我们可以好好想想，上面M\[j\] == M\[k\]时候，直接+1

就能够得到我的next，此处不相等，那么我们可以从M前面串的字串来处理，也就是说有可能从 M\[ next\[k\] \]

下面写下代码：

#include <stdio.h>
    #include <string.h>
    
    void get_next( char *tmp,int *next )
    {
        int j,k;
        int len = strlen( tmp );
    
        next[0] = -1;                            // 初始化 
        j = 0;
        k = -1;
    
        while( j < len - 1 )
        {
            if( k == -1 || tmp[j] == tmp[k] )    // tmp[j]==tmp[k]
            {
    			j++;
    			k++;
    
                if( tmp[j] == tmp[k] )	   // if相等，那么和前面的next是一样
    	    {                               
                    next[j] = next[k];
    	    }
                else
    	    {
                    next[j] = k;                
    	    }
            }
            else                   
    	{
                k = next[k];                    // 长串不匹配，那么可以看看子串有没有匹配的！ 
    	}
        }
    }
    
    int KMP( char *s,char *tmp, int next[] )
    {
        int i = 0,j = 0, len_s = strlen( s ), len_p = strlen( tmp );
    
        while( i < len_s )
        {
            if( j == -1 || s[i] == tmp[j] )  // 刚刚进来 || 此个char匹配上 
            {
                i++;
                j++;
            }
            else
            {
                j = next[j];       // 消除了指针i的回溯( 不同于BF的地方 )
            }
    
            if( j == len_p )       // 匹配结束 
    	{
                return i - len_p;  // 返回匹配位置
    	}
        }
    
        return -1;                 // 没有找到
    }
    
    
    
    int main()
    {
    	char str[80], sub_str[20];
    	int  next[100], first_at;
    
    	while( gets( str ) )
    	{
    		gets( sub_str );
    		
    		get_next( sub_str,next );             // 递推法求next数组 
    		first_at = KMP( str, sub_str, next ); //  
    
    		if( first_at != -1 )
    		{
    			printf("At: %d\n", first_at);
    		}
    		else
    		{
    			printf("No cmp...\n");
    		}
    	}
    
    	return 0;
    }

[http_blog.csdn.net_shanshanpt_article_details_8679459]: http://blog.csdn.net/shanshanpt/article/details/8679459