现在的位置: 首页 > 综合 > 正文

KMP小讲 【理解 + 例题】 更新 ing…..

2019年02月19日 ⁄ 综合 ⁄ 共 1359字 ⁄ 字号 评论关闭

         看到这个,你也许会问,为什么是小讲,因为渣渣只能是小讲,所以......................

         KMP对于学算法的人来说,是一道坎(至少对于我来说)。下面贴一下学习资料

         简单易懂    http://kb.cnblogs.com/page/176818/

         稍微好懂   http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

         严蔚敏视频  http://www.56.com/u59/v_NjAwMzA0ODA.html

        我先接着看了KMP了, 具体的个人理解和例题会持续贴出 .....................

        这几天天天熬夜, 黑黑的眼圈,却没有一点收获。

       理解麻烦,先贴几道题木吧,贴完就睡觉......

       相信看完上面的  有一定的理解了吧  水题的话,就是对next数组的稍加理解和应用吧 下面第一题    

       第一题  HDU 2584  Simpsons’ Hidden Talents      http://acm.hdu.edu.cn/showproblem.php?pid=2594   

       题意:第一个字符串的前缀和第二个字符串的后缀的最大相同。

       思路:将两个字符串合并,直接一次获得next数组就可以了,主要是对next数组代表的意思的理解吧

     

//  HDU 2584  Simpsons’ Hidden Talents
//  By   xi_long 
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;

#define MAX 50010

char str1[MAX << 1];
char str2[MAX];
int next[MAX << 1];

void get_next(char *p)
{
	int i = 0,j = -1;
	next[0] = -1;
	int len = strlen(p);
	while(i < len)
	{
		if(j == -1 || p[i] == p[j])
		{
			i++;
			j++;
	        next[i] = j;
		}
		else
		   j = next[j];
	}
}

int main()
{
    int n, m;
    while(~scanf("%s%s",str1, str2))
    {
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        strcat(str1, str2);                 //  string 的函数, 合并str1和str2
        get_next(str1);
        int len = len1 + len2;
        while(next[len] > len1 || next[len] > len2)
            len = next[len];                // 找到最长的
        if(next[len])
        {
            for(int i = 0; i < next[len]; i ++)
                printf("%c",str1[i]);
            printf(" %d\n",next[len]);
        }
        else
            printf("0\n");
    }
    return 0;
}

    

--------------------------------------------  渣渣的算法路 , 大神勿喷, 欢迎一起交流 , 有事请留言

   

抱歉!评论已关闭.