题目大意
给出一个模式串n为01串,求问长度为m的所有文本串中有多少长度为n的子串能做到与模式串近似匹配。
近似匹配的意思为:最多只有一个字符与模式串不同。
题解
我们是无法在短时间内强行进行近似匹配的,所以只能转化成完全匹配来做。
最多只有一个字符与模式串不同,这样我们就可以把模式串写成n+1个不同的模式串,即原模式串每个字符都变换一次,作为一个新的模式串。
多模式串匹配问题,一定是AC自动机。
我们把所有的模式串合起来建立一个AC自动机,在上面跑DP就可以了。
我们设dp[i][j]表示当前遍历文本串的第i位,到达AC自动机状态j的方案数。
当然这样空间是不够用的,所以需要用滚动数组优化掉第一维的空间。
对于上一位的状态j,假设当前位到达状态为next[j][k],k为枚举的第i位的字符;
若当前状态为终结状态,则总方案数ans += dp[i-1&1][j] * (1ll << (m-i))
若当前状态非终结状态,则有转移dp[i&1][next[j][k]] += dp[i-1&1][j];
直接DP即可。
代码
#include <bits/stdc++.h> const int maxn = 2e3 + 5; using namespace std; typedef long long ll; int nex[maxn][2], fail[maxn], ed[maxn], flag[maxn]; int root, p; inline int newnode() { for (int i = 0; i < 2; ++i) { nex[p][i] = -1; } ed[p++] = 0; return p - 1; } inline void init() { p = 0; root = newnode(); } inline void insert(char *buf) { int now = root; for (int i = 0; buf[i]; ++i) { if (nex[now][buf[i]-'0'] == -1) nex[now][buf[i]-'0'] = newnode(); now = nex[now][buf[i]-'0']; } ed[now] = 1; flag[now] = 1; } void build() { queue<int> que; fail[root] = root; for (int i = 0; i < 2; ++i) { if (nex[root][i] == -1) nex[root][i] = root; else { fail[nex[root][i]] = root; que.push(nex[root][i]); } } while (!que.empty()) { int now = que.front(); que.pop(); for (int i = 0; i < 2; ++i) { if (nex[now][i] == -1) nex[now][i] = nex[fail[now]][i]; else { fail[nex[now][i]] = nex[fail[now]][i]; if(ed[nex[fail[now]][i]]) ed[nex[now][i]] = 1; que.push(nex[now][i]); } } } } int T; ll n,m; char s[maxn]; ll dp[2][maxn]; int main(){ scanf("%d",&T); while(T--){ init(); scanf("%lld%lld",&n,&m); scanf("%s",s); insert(s); for(int i = 0;i < n;++i){ if(s[i] == '1') s[i] = '0'; else s[i] = '1'; insert(s); if(s[i] == '1') s[i] = '0'; else s[i] = '1'; } build(); ll ans = 0; dp[0][0] = 1; for(int i = 1;i <= m;++i){ for(int j = 0;j < p;++j)dp[i & 1][j] = 0; for(int j = 0;j < p;++j){ if(ed[j])continue; for(int k = 0;k < 2;++k){ if(ed[nex[j][k]]){ ans += dp[i + 1 & 1][j] * (1ll << (m - i)); } else{ dp[i&1][nex[j][k]] += dp[i+1&1][j]; } } } } for(int i = 0;i < p;++i){ dp[0][i] = dp[1][i] = 0; } printf("%lld\n",ans); } return 0; }
No Leanote account ? Sign up now.