kmp1-HDU1711 HDU1686 HDU2087 HDU3746

叁歲伎倆 2022-05-14 11:24 196阅读 0赞

HDU 1711 kmp模板题

[http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_showproblem.php_pid_1711]

#include<stdio.h>
    #include<string.h>
    #define N 1000005
    int s[N];
    int p[N];
    int next[N];
    int m,n;
    void getnext(){
        int j=0,k=-1;
        next[0]=-1;
        while(j<m){
            if(k==-1||p[j]==p[k]){
                j++;
                k++;
                next[j]=k;
            }
            else
                k=next[k];
        }
    }
    int kmp(){
        int i=0,j=0;
        getnext();
        while(i<n){
            if(j==-1||s[i]==p[j]){
                i++;
                j++;
            }
            else
                j=next[j];
            if(j==m)
                return i;
        }
        return -1;
    }
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++)
                scanf("%d",&s[i]);
            for(int i=0;i<m;i++)
                scanf("%d",&p[i]);
            if(kmp()==-1)
                printf("-1\n");
            else
                printf("%d\n",kmp()-m+1);
        }
        return 0;
    }

HDU1686

[http://acm.hdu.edu.cn/showproblem.php?pid=1686][http_acm.hdu.edu.cn_showproblem.php_pid_1686]

题意就是，给你一个字符串A，一个字符串B，求A在B中总共出现了几次，注意，重复的也算。

稍微改动即可。

**HDU 2087 剪花布条(KMP:贪心)**

**[http://acm.hdu.edu.cn/showproblem.php?pid=2087][http_acm.hdu.edu.cn_showproblem.php_pid_2087]**

直接用KMP算法,用T模式串去匹配S主串即可，但是当匹配成功的时候要看看当前匹配点离上一个匹配点是不是距离差>=T的长度。

贪心，从左向右依次选取即可，证明略。

#include <iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int MAXN=1000+100;
    char S[MAXN],T[MAXN];
    int next[MAXN];
    int n,m;
    int cnt,last;
    void getFail()
    {
        next[0]=next[1]=0;
        for(int i=1;i<m;i++)
        {
            int j=next[i];
            while(j && T[i]!=T[j]) j=next[j];
            next[i+1] = (T[i]==T[j])?j+1:0;
        }
    }
    void KMP()
    {
        n=strlen(S);
        m=strlen(T);
        getFail();
        int j=0;
        for(int i=0;i<n;i++)
        {
            while(j && S[i]!=T[j]) j=next[j];
            if(S[i]==T[j]) j++;
            if(j==m)
            {
                if(cnt==0)
                {
                    cnt++;
                    last=i;//last指向匹配位置的末尾
                }
                else if(i-last>=m)
                {
                    cnt++;
                    last=i;
                }
            }
        }
    }
    int main()
    {
        while(scanf("%s",S)==1)
        {
            if(strcmp(S,"#")==0)
                break;
            scanf("%s",T);
            cnt=0;
            KMP();
            printf("%d\n",cnt);
        }
        return 0;
    }

HDU3746 next应用

[http://acm.hdu.edu.cn/showproblem.php?pid=3746][http_acm.hdu.edu.cn_showproblem.php_pid_3746]

逻辑就是找到最长相同前后缀再在后面加上那一段就找到了.

注意：用原始next，next数组存的是前缀和后缀的最大匹配值，

比如abcabca

改进前最后一个字符next\[7\]=4,表示的是前缀和后缀最大匹配是4，即abca和abca。

改进后的next\[7\]=-1。

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define N 100010
     
    char s[N];
    int nextval[N];
    int len;
     
    void getnext(const char *s)
    {
    	int i = 0, j = -1;
    	nextval[0] = -1;
    	while(i != len)
    	{
    		if(j == -1 || s[i] == s[j])
    			nextval[++i] = ++j;
    		else
    			j = nextval[j];
    	}
    }
     
    int main()
    {
    	int ncase;
    	int length, add;
    	scanf("%d", &ncase);
    	while(ncase--)
    	{
    		scanf("%s", s);
    		len = strlen(s);
    		getnext(s);
    		/*for(int i = 0; i <= len; ++i) //查看next数组的内容
    			cout<<nextval[i]<<" ";
    		cout<<endl;*/
    		length = len - nextval[len]; //循环节的长度
    		if(len != length && len % length == 0) //循环多次
    			printf("0\n");
    		else
    		{
    			add = length - nextval[len] % length; //取余的作用：abcab，去掉abc
    			printf("%d\n",add);
    		}
    	}
    	return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1711]: http://acm.hdu.edu.cn/showproblem.php?pid=1711
[http_acm.hdu.edu.cn_showproblem.php_pid_1686]: http://acm.hdu.edu.cn/showproblem.php?pid=1686
[http_acm.hdu.edu.cn_showproblem.php_pid_2087]: http://acm.hdu.edu.cn/showproblem.php?pid=2087
[http_acm.hdu.edu.cn_showproblem.php_pid_3746]: http://acm.hdu.edu.cn/showproblem.php?pid=3746