HDU 5763：Another Meaning（字符串匹配） Another Meaning

http://acm.hdu.edu.cn/showproblem.php?pid=5763

Problem Description

As is known to all, in many cases, a word has two meanings. Such as “hehe”, which not only means “hehe”, but also means “excuse me”.
Today, ?? is chating with MeiZi online, MeiZi sends a sentence A to ??. ?? is so smart that he knows the word B in the sentence has two meanings. He wants to know how many kinds of meanings MeiZi can express.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each test case contains two strings A and B, A means the sentence MeiZi sends to ??, B means the word B which has two menaings. string only contains lowercase letters.

Limits

T <= 30
|A| <= 100000
|B| <= |A|

Output

For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the number of the different meaning of this sentence may be. Since this number may be quite large, you should output the answer modulo 1000000007.

Sample Input

hehehe

hehe

woquxizaolehehe

woquxizaole

hehehehe

hehe

owoadiuhzgneninougur

iehiehieh

Sample Output

Case #1: 3

Case #2: 2

Case #3: 5

Case #4: 1

Hint

In the first case, “ hehehe” can have 3 meaings: “*he”, “he*”, “hehehe”. In the third case, “hehehehe” can have 5 meaings: “*hehe”, “he*he”, “hehe*”, “**”, “hehehehe”.

题意：每个例子的第二个串有两个意思，然后求第一个串可以表达多少种意思。

思路：做的时候DP方程推不出来，太渣了。dp[i]表示以i结尾长度的串有多少种意思，如果不替换的话，dp[i] = dp[i-1]，如果当前匹配的话可以替换，要加上前面的dp[i-m]，赛后补题的时候发现string类有个substr的函数很厉害。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 #include <iostream>
 6 using namespace std;
 7 #define N 100005
 8 #define MOD 1000000007
 9 /*
10 对于这个问题，显然可以进行DP：
11 令dp[i]表示到i结尾的字符串可以表示的不同含义数，那么考虑两种转移:
12 
13 末尾不替换含义：dp[i - 1]
14 
15 末尾替换含义：dp[i - |B|]  (A.substr(i - |B| + 1,|B|) = B)
16 
17 那么对于末尾替换含义的转移，需要快速判断BB能不能和当前位置的后缀匹配，kmp或者hash判断即可。
18 
19 复杂度:O(N)
20 */
21 long long dp[N];
22 string s, str;
23 
24 int main()
25 {
26     int t;
27     cin >> t;
28     for(int cas = 1; cas <= t; cas++) {
29         memset(dp, 0, sizeof(dp));
30         cin >> s >> str;
31         int n = s.size();
32         int m = str.size();
33         for(int i = 0; i < m; i++)
34             dp[i] = 1;
35         for(int i = m; i <= n; i++) {
36             dp[i] = dp[i-1];
37             string ss = s.substr(i - m, m);
38             if(ss == str)
39                 dp[i] += dp[i-m] % MOD;
40             dp[i] %= MOD;
41         }
42         printf("Case #%d: ", cas);
43         cout << dp[n] << endl;
44     }
45     return 0;
46 }

HDU 5763：Another Meaning（字符串匹配） Another Meaning

相关推荐