http://acm.hdu.edu.cn/showproblem.php?pid=5745
这题好劲爆啊。dp容易想，但是要bitset优化，就想不到了。
先放一个tle的dp。复杂度O(n * m)的
第一个串，记作str[]，第二个记作sub[]
思路就是，设dp[i][j][k]表示，匹配了sub的前i个，以str的第j个结尾，然后sub[i]有三种状态，0表示不变化，1表示和前一个，2表示和后一个。
那么以求dp[i][j][0]为列
因为需要的是判断str的第j个结尾是否和sub的前i个完全匹配。
那么，要使得dp[i][j][0]为true，必然需要前i - 1个和j - 1个匹配成功。就是要递推过来。
那么dp[i][j][0] = (dp[i - 1][j - 1][0] || dp[i - 1][j - 1][1]) && (str[j] == sub[i])
其他的类似啦。
可以滚动下数组。
不清0的话，直接用DFN代替即可。这样的复杂度就是O(n * m)，没有常数。但是还是TLE.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e5 + ;
char str[maxn], sub[maxn];
int dp[][maxn][];
int DFN;
char ans[maxn];
void work() {
DFN++;
int lenstr, lensub;
scanf("%d%d", &lenstr, &lensub);
scanf("%s", str + );
scanf("%s", sub + );
// dp[0][0][0] = DFN;
for (int i = ; i <= lenstr; ++i) dp[][i][] = DFN;
int now = ;
for (int i = ; i <= lensub; ++i) {
now = !now;
for (int j = ; j <= lenstr; ++j) {
// if ((dp[i - 1][j - 1][0] || dp[i - 1][j - 1][1]) && str[j] == sub[i]) {
// dp[i][j][0] = true;
// }
// if (dp[i - 1][j - 1][2] && str[j] == sub[i - 1]) {
// dp[i][j][1] = true;
// }
// if ((dp[i - 1][j - 1][0] || dp[i - 1][j - 1][1]) && sub[i + 1] == str[j]) {
// dp[i][j][2] = true;
// }
if ((dp[!now][j - ][] == DFN || dp[!now][j - ][] == DFN) && str[j] == sub[i]) {
dp[now][j][] = DFN + ;
}
if (dp[!now][j - ][] == DFN && str[j] == sub[i - ]) {
dp[now][j][] = DFN + ;
}
if ((dp[!now][j - ][] == DFN || dp[!now][j - ][] == DFN) && str[j] == sub[i + ]) {
dp[now][j][] = DFN + ;
}
}
DFN++;
}
for (int i = ; i <= lenstr; ++i) {
ans[i] = '';
if (dp[now][i][] == DFN || dp[now][i][] == DFN || dp[now][i][] == DFN) {
// printf("1");
ans[i - lensub + ] = '';
}
}
ans[lenstr + ] = '\0';
printf("%s\n", ans + );
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
然后百度了一个bitset的优化。
考虑用bitset<1e5> dp[5000][k]
dp[i][k]
表示，处理了sub的前i个，当前sub的状态是k，然后匹配整个str串的结果就是dp[i][k]，因为dp[i][k]是一个长度为1e5的01串嘛。也就是dp[i][k]就是匹配好的结果了。
那么，要快速计算dp[i][0]，只需要(dp[i - 1][0] | dp[i - 1][1]) << 1
比如前2个匹配好的结果是"10"和"11"然后匹配成的第三位，就是"011"，关键看看第三位，是1,也就是上面的dp[i - 1][j - 1][k] = true的意思。就是前面的匹配好了，但是还要看看str[j]和sub[i]的相等情况。
要想这一位是true，必然要这一位和sub对应相等。但是我们一次要算出整一个结果，而不是一个一个地算，那么，预处理个pos[26]的bitset就可以，&一下，就是要对应位置是1的，才是true。
3478ms，我是卡过去的
后来一直TLE
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset> const int maxn = 1e5 + ;
bitset<maxn> dp[][];
char str[maxn], sub[maxn];
bitset<maxn>pos[]; void init() {
for (int i = ; i <= ; ++i) {
for (int j = ; j <= ; ++j) {
dp[i][j].reset();
}
}
for (int i = ; i < ; ++i) pos[i].reset();
}
char ans[maxn];
void work() {
init();
int lenstr, lensub;
scanf("%d%d", &lenstr, &lensub);
scanf("%s%s", str + , sub + );
for (int i = ; i <= lenstr; ++i) {
pos[str[i] - 'a'][i] = ;
}
dp[][] = pos[sub[] - 'a'];
if (lensub >= ) dp[][] = pos[sub[] - 'a'];
int now = ;
for (int i = ; i <= lensub; ++i) {
now = !now;
dp[now][] = ((dp[!now][] | dp[!now][]) << ) & pos[sub[i] - 'a'];
dp[now][] = (dp[!now][] << ) & pos[sub[i - ] - 'a'];
if (i < lensub) {
dp[now][] = ((dp[!now][] | dp[!now][]) << ) & pos[sub[i + ] - 'a'];
}
}
for (int i = ; i <= lenstr; ++i) {
if (i + lensub - > lenstr) {
ans[i] = '';
} else {
if (dp[now][][i + lensub - ] || dp[now][][i + lensub - ]) {
ans[i] = '';
} else ans[i] = '';
}
}
ans[lenstr + ] = '\0';
printf("%s\n", ans + );
// printf("\n");
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}