[HDU5763]Another Meaning

Posted on | In

话说这道题考场上把我弄自闭了

$KMP$板子有点忘记了，强行回忆了一波

然后突然发现不会计数。。。

不会$DP$的我就自闭了，其实这题$DP$式子不是一般的简单

先把子串的$Fail$指针预处理出来

然后在母串中匹配出子串的位置

最后进行$DP$计数，转移方程$F$$[$$i$$]$$=$$F$$[$$i-1$$]$$+$$F$$[$$i-m$$]$

其中$i$是母串中成功匹配的位置，$m$为子串的长度

因为每匹配一次子串，都会带来新的意思，加上这个子串的方案数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
char s[200002];
char t[200002];
int m,n,T;
int f[200002];
int fail[200002];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",s+1,t+1);
        n=strlen(s+1);m=strlen(t+1);
        for(register int i=2;i<=m;++i)
        {
            int j=fail[i-1];
            while(j&&t[j+1]!=t[i]) j=fail[j];
            if(t[j+1]==t[i]) ++j;
            fail[i]=j;
        }
        f[0]=1;
        for(register int i=1,j=0;i<=n;++i)
        {
            while(j&&s[i]!=t[j+1]) j=fail[j];
            if(s[i]==t[j+1]) ++j;
            if(j==m) j=fail[j],f[i]=f[i-m];
            f[i]+=f[i-1];
            f[i]-=f[i]>=mod?mod:0;
        }
        printf("%d\n",f[n]);
        memset(f,0,sizeof(f));
        memset(fail,0,sizeof(fail));
    }
    return 0;
}