hdu 5763 || 2016 multi #4 1001 Another Meaning (kmp+dp)
题意：给定两个字符串A和B，每个出现在A中的B(可以overlap)都有两种含义，问A串一共可能有多少种含义。
思路：kmp+dp.
考虑dp[i]为前i个字符（也就是从开始长度为i，注意不是字符串的下标为i）的含义数。
我们考虑第i个字符对其他位置字符的贡献。
首先第i位的含义数可以无条件得转移到i+1位。也就是dp[i+1]+=dp[i];
此外，如果第i位是一个B串开始的位置，那么第i位对i+len2位就有贡献。也就是dp[i+len2]+=dp[i];
初始化dp[0]=1，其他为0.
剩下我们要做的就是处理出A串中的哪些位置是B串开始的位置。
kmp处理下就好，用一个布尔数组标记。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月11日 星期四 11时07分24秒
4File Name :code/hdu/5763.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int MOD = 1E9+7;
34const int N=1E5+7;
35int nxt[N];
36char a[N],b[N];
37bool v[N];
38int dp[N];
39void getnxt(char *s)
40{
41 int i = 0;
42 int j = -1;
43 nxt[0] = -1;
44 int n = strlen(s);
45 while (i<n)
46 if (j==-1||s[i]==s[j]) nxt[++i]=++j;
47 else j = nxt[j];
48}
49void kmp( char *a,char *b)
50{
51 int n = strlen(a);
52 int m = strlen(b);
53 getnxt(b);
54 int i = 0 ;
55 int j = 0 ;
56 while (i<n)
57 {
58 if (j==-1||a[i]==b[j]) i++,j++;
59 else j = nxt[j];
60 if (j==m)
61 {
62 v[i-m] = true;//长度为i的位置的下标是i-1,开始的位置是（i-1）+m+1,也就是i-m
63// cout<<"i:"<<i<<" i-m:"<<i-m<<endl;
64 }
65 }
66}
67int main()
68{
69 #ifndef ONLINE_JUDGE
70 freopen("code/in.txt","r",stdin);
71 #endif
72 int T;
73 cin>>T;
74 int cas = 0;
75 while (T--)
76 {
77 printf("Case #%d: ",++cas);
78 scanf("%s",a);
79 scanf("%s",b);
80 ms(v,false);
81 kmp(a,b);
82 int len1 = strlen(a);
83 int len2 = strlen(b);
84 ms(dp,0);
85// for ( int i = 0 ; i < len1 ; i++) cout<<i<<" "<<v[i]<<endl;
86
87 dp[0] = 1; //dp[i]表示长度为i为止的方案数(注意是长度为i，不是字符串下标为i!!!)
88 for ( int i = 0 ; i < len1; i++) //这样考虑比较容易，我们考虑第i位的贡献。
89 { //第i位的贡献无论如何都可以传递到下一位。如果第i位是某个匹配开始的位置，还可以传递到i+len2-1的位置。
90 dp[i+1] = (dp[i+1] + dp[i])%MOD;
91 if (v[i]) dp[i+len2] = (dp[i+len2] + dp[i]) % MOD;
92 }
93// for ( int i = 0 ; i <= len1 ; i++) cout<<i<<" dp[i]:"<<dp[i]<<endl;
94 printf("%d\n",dp[len1]%MOD);
95 }
96 #ifndef ONLINE_JUDGE
97 fclose(stdin);
98 #endif
99 return 0;
100}