HDU 5763 Another Meaning
题意：一个字串有可能在模式串出现多次，问有多少种可能出现的情况。关键是有重合的字串是不能同时计入的。
思路：先用kmp求出所有字串的位置。然后，dp.
二维的时候：dp[i][j] i表示前i个子串，j的值1表示一定用这个串，0表示不用。值表示字串出现的情况数。
一维的时候可以直接用dp[i] 表示前i个字串能出现的情况。
然后，状态转移就都是分为三种情况：
1）当前子串和前一个子串不冲突，dp[i] = dp[i-1] * 2. 或者 dp[i][0] = dp[i-1][1] + dp[i-1][0] = dp[i][1] = dp[i-1][1].
2) 当前子串和前一个冲突，那就不一定是只和前一个冲突，所以从i-2开始寻找直到找到不冲突的j，有 dp[i] = dp[i-1] + dp[j]. 或者 dp[i][0] = dp[i-1][1] + dp[i-1][0] , dp[i][1] = dp[j][0] + dp[j][1].
3) 当前子串没找到上述的j子串，那么dp[i] = dp[i-1] + 1. 或者 dp[i][1] = 1.
二维代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
vector <int> ans;
vector <int> find_substring(string pattern, string text) {
int n = pattern.size();
vector <int> nxt(n+1, 0);
for (int i=1; i<n; ++i) {
int j = i;
while(j > 0) {
j = nxt[j];
if (pattern[j] == pattern[i]) {
nxt[i+1] = j + 1;
break;
}
}
}
vector <int> positions;
int m = text.size();
for (int i=0, j=0; i<m; ++i) {
if (j<n && text[i] == pattern[j]) {
j++;
}else {
while (j>0) {
j = nxt[j];
if (text[i] == pattern[j]) {
j++;
break;
}
}
}
if (j == n) {
positions.push_back(i-n+1);
}
}
return positions;
}
int dp[100005][2]; // dp[i][1] 表示前i个串一定用上第i个时 maxans dp[i][0] 表示前i个串的时候不用第i个时候的ans.
int main() {
int t;
//freopen("in.cpp", "r", stdin);
cin >> t;
string str1, str2;
int cas = 0;
while(t--) {
ans.clear();
cin >> str1 >> str2;
ans = find_substring(str2, str1);
int tot = ans.size();
if (tot == 0) {
printf("Case #%d: %d
", ++cas, 1);
continue;
}
dp[0][0] = 1;
dp[0][1] = 1;
for (int i=1; i<tot; ++i) {
dp[i][0] = ((dp[i-1][0]%mod) + (dp[i-1][1]%mod))%mod;
bool flag = false;
for (int j=i-1; j>=0; --j) {
if (ans[i] - ans[j] >= str2.length()) {
dp[i][1] = ((dp[j][1]%mod) + (dp[j][0]%mod)) % mod;
flag = true;
break;
}
}
if (flag == false) {
dp[i][1] = 1;
}
}
// if(ans[i]-ans[i-1]>=str2.length())dp[i][1]=(dp[i][1]%mod+dp[i-1][1]%mod)%mod;
printf("Case #%d: %d
", ++cas, ((dp[tot-1][1]%mod)+(dp[tot-1][0]%mod))%mod);
}
return 0;
}
一维代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
vector <int> ans;
vector <int> find_substring(string pattern, string text) {
int n = pattern.size();
vector <int> nxt(n+1, 0);
for (int i=1; i<n; ++i) {
int j = i;
while(j > 0) {
j = nxt[j];
if (pattern[j] == pattern[i]) {
nxt[i+1] = j + 1;
break;
}
}
}
vector <int> positions;
int m = text.size();
for (int i=0, j=0; i<m; ++i) {
if (j<n && text[i] == pattern[j]) {
j++;
}else {
while (j>0) {
j = nxt[j];
if (text[i] == pattern[j]) {
j++;
break;
}
}
}
if (j == n) {
positions.push_back(i-n+1);
}
}
return positions;
}
int dp[100005];
int main() {
int t;
//freopen("in.cpp", "r", stdin);
cin >> t;
string str1, str2;
int cas = 0;
while(t--) {
ans.clear();
cin >> str1 >> str2;
ans = find_substring(str2, str1);
int tot = ans.size();
if (tot == 0) {
printf("Case #%d: %d
", ++cas, 1);
continue;
}
dp[0] = 2;
for (int i=1; i<tot; ++i) {
if (ans[i]-ans[i-1]>=str2.length()) {
dp[i] = (dp[i-1]*2)%mod;
}
else {
bool flag = true;
for (int j=i-2; j>=0; --j) {
if (ans[i] - ans[j] >= str2.length()) {
dp[i] = (dp[j] + dp[i-1])%mod;
flag = false;
break;
}
}
if (flag) dp[i] = (dp[i-1] + 1)%mod;
}
}
printf("Case #%d: %d
", ++cas, dp[tot-1]%mod);
}
return 0;
}
体验：dp无处不在..dp大法好... >_<