给你串A和串B，|B| <= |A|
已知串B有两种可能含义，求串A的总可能含义数
dp[i]表示串A的从头开始长度为i的串的可能意义的数目
若该长度为i的串的后缀与模式串B匹配，则该后缀可以选择替换或者不替换
dp[i] = dp[i - 1] + dp[i - Bl] 否则dp[i] = dp[i - 1]
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define INF 0x3f3f3f3f 8 #define MOD 1000000007 9 using namespace std;10 typedef long long LL;11 typedef unsigned long long ULL;12 const int maxn = 1e5 + 10;13 char s1[maxn], s2[maxn];14 int dp[maxn];15 const ULL B = 100000007;16 17 void contain(char *a, char *b) {18 int al = strlen(a), bl = strlen(b);19 ULL t = 1;20 for (int i = 0; i < al; i++) t *= B;21 ULL ah = 0, bh = 0;22 for (int i = 0; i < al; i++) ah = ah * B + a[i];23 for (int i = 0; i < al; i++) bh = bh * B + b[i];24 25 memset(dp, 0, sizeof(dp));26 for (int i = 0; i < al; i++) dp[i] = 1;27 28 for (int i = 0; i + al <= bl; i++) {29 dp[i + al] = dp[i + al - 1];30 if (ah == bh) {31 dp[i + al] = (dp[i + al] + dp[i]) % MOD;32 }33 if (i + al < bl) bh = bh * B + b[i + al] - b[i] * t;34 }35 }36 37 38 int main(int argc, const char * argv[]) {39 int T;40 scanf("%d", &T);41 for (int t = 1; t <= T; t++) {42 scanf("%s%s", s1, s2);43 contain(s2, s1);44 int l1 = strlen(s1);45 printf("Case #%d: ", t);46 printf("%d\n", dp[l1]);47 48 }49 return 0;50 }