DP-HDU-5763-Another Meaning

2023-10-17 07:08

文章标签 dp hdu another 5763 meaning

本文主要是介绍DP-HDU-5763-Another Meaning，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Another Meaning

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 46 Accepted Submission(s): 14

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
4
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”.

Author
FZU

Source
2016 Multi-University Training Contest 4

题意：
给一个字符串，同时给一个单词串，这个单词串会有两种意思，问字符串总共可能有多少种意思。

题解：
一开始没读懂题意，正确的意思应该是如果字符串中出现了匹配的单词串，那么可以合并成一个新的意思，也可以保留原来的不变，那么很容易得出DP的状态转移。dp[i]表示字符串中以第i位结尾的前缀子串会有多少种不同的意思。
令单词串的长度为L。那么对于字符串的第i位，如果以第i位为末尾之前的L长度的串恰好匹配单词串，那么一定可以把这L长度合并为一个新的意思，于是dp[i]+=dp[i-L]。如果不合并，那么还有一种意思是原意，即dp[i]+=dp[i-1]。最后输出最后一位即可。

//
//  main.cpp
//  160728-3
//
//  Created by 袁子涵 on 16/7/28.
//  Copyright © 2016年 袁子涵. All rights reserved.
//#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>using namespace std;
const int MOD=1000000007;
long long int out,L1,L2,total,tmp;
long long int dp[100005];
string str,mode;
int main(int argc, const char * argv[]) {int t,cas=0;cin >> t;while (t--) {cas++;total=0;cin >> str >> mode;L1=str.length();L2=mode.length();for (long long int i=0; i<L2; i++)dp[i]=1;for (long long int i=L2; i<=L1; i++) {dp[i]=dp[i-1];string tt=str.substr(i-L2,L2);if (tt==mode)dp[i]+=dp[i-L2];dp[i]%=MOD;}cout << "Case #" << cas << ": " << dp[L1] << endl;}return 0;
}