首页 > 其他 > 详细

hdu5763 kmp+dp

时间:2016-07-29 17:06:34      阅读:272      评论:0      收藏:0      [点我收藏+]

先说说kmp模板,本质就是先求小字符串的next数组,即对每个位置i,next[i]以i位置为终点,前缀和后缀相等的最大长度

求出之后以小字符串为基准类似去求大字符串的next,从而根据需要的到数据

参考博客 http://www.cnblogs.com/c-cloud/p/3224788.html

 

题意就是给你两个字符串,A,B,A中每一个B字符串都有两种意思,问A总共可以有多少种意思
令dp[i]表示到i结尾的字符串可以表示的不同含义数,那么考虑两种转移:
末尾不替换含义:dp[i - 1]
末尾替换含义:dp[i - |B|] (A.substr(i - |B| + 1,|B|) = B)
那么对于末尾替换含义的转移,需要快速判断BB能不能和当前位置的后缀匹配,kmp或者hash判断即可。

#include <iostream>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <set>
#include<stdio.h>

using namespace std;
const int N=1e5+10;
const int M=1e9+7;
char s[N],t[N];
int T,cas,p[N],nt[N],dp[N];
void makeNext()//求next数组,即小字符串中每个位置i,1~i中最长的前缀和后缀相等的长度
{
    int q,k;
    int m = strlen(t+1);
    nt[1] = 0;//下标注意
    for (q = 2,k = 0; q <= m; ++q)//q值注意
    {
        while(k > 0 && t[q] != t[k+1])//这里注意因为代码求得的字符串是从一开始所以是k+1,从0开始应为k,相应k变成k-1
            //其实就是字符串上移动一位后该与哪位比较,自己仔细看看,但是当k作为长度时是不变的,只有做数组下标时改变
            k = nt[k];//下标改变
        if (t[q] == t[k+1])//下标改变
        {
            k++;
        }
        nt[q] = k;
    }
}

void kmp()
{
    int n,m;
    int i,q;
    n = strlen(s+1);
    m = strlen(t+1);
    makeNext();
    for (i = 1,q = 0; i <= n; ++i)//i值
    {
        while(q > 0 && t[q+1] != s[i])//此处为q,一样的意思
            q = nt[q];//下标改变
        if (t[q+1] == s[i])//下标改变
            q++;
        p[i]=q;
        if (q == m)
            q=nt[q];//下标不改变
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    cin>>T;
    while(T--)
    {
        cas++;
        scanf("%s%s",s+1,t+1);
        int sl=strlen(s+1),tl=strlen(t+1);
        kmp();//kmp模板
        dp[0]=1;
        for(int i=1; i<=sl; i++)
            if(p[i]>=tl) dp[i]=dp[i-1]+dp[i-tl],dp[i]%=M;
            else dp[i]=dp[i-1];
        printf("Case #%d: %d\n",cas,dp[sl]);
    }
    return 0;
}

 

hdu5763 kmp+dp

原文:http://www.cnblogs.com/shimu/p/5718939.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!