Codechef CLHMSG Hidden Message KMP+动态规划

将\(W\)编码得到\(W_e\)。动态规划，\(f_1[i]\)表示\(S[1..i]\)的译码方案数，\(f_2[i]\)表示\(S[i..len(S)]\)的译码方案数。设\(W_e\)在\(S\)中的出现的起始位置集合为\(M\)，则答案为\(\sum\limits_{m_i \in M} f_1[m_i-1] \times f_2[m_i+len(W_e)]\)。时间复杂度\(O(n)\)。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int mod = 1000000007;

char s1[10];
char s[400010],w[400010],we[2000010],nxt[2000010];
int f1[400010],f2[400010];

int main() {
    int T;
    scanf("%d",&T);
    for (; T--;) {
        scanf("%s%s",s + 1,w + 1);
        int n = strlen(s + 1),m = strlen(w + 1);
        int m1 = 0;
        for (int i = 1; i <= m; i++) {
            int x = w[i] - 'a' + 1;
            int l = m1 + 1;
            for (; x > 0; x >>= 1)
                we[++m1] = (x & 1) + '0';
            reverse(we + l,we + m1 + 1);
        }
        we[m1 + 1] = 0;
        if (m1 > n) {
            puts("0");
            continue;
        }
        for (int i = 2,j = 0; i <= m1; i++) {
            for (; j > 0 && we[j + 1] != we[i]; j = nxt[j]);
            if (we[j + 1] == we[i])
                j++;
            nxt[i] = j;
        }
        f1[0] = 1;
        for (int i = 1; i <= n; i++) {
            f1[i] = 0;
            for (int j = 1; j <= 26; j++) {
                int tot = 0,x = j;
                for (; x > 0; x >>= 1)
                    s1[++tot] = (x & 1) + '0';
                reverse(s1 + 1,s1 + tot + 1);
                if (i - tot >= 0) {
                    bool flag = 1;
                    for (int j = 1; j <= tot; j++)
                        if (s[i - tot + j] != s1[j]) {
                            flag = 0;
                            break;
                        }
                    if (flag)
                        f1[i] = (f1[i] + f1[i - tot]) % mod;
                }
            }
        }
        f2[n + 1] = 1;
        for (int i = n; i >= 1; i--) {
            f2[i] = 0;
            for (int j = 1; j <= 26; j++) {
                int tot = 0,x = j;
                for (; x > 0; x >>= 1)
                    s1[++tot] = (x & 1) + '0';
                reverse(s1 + 1,s1 + tot + 1);
                if (i + tot <= n + 1) {
                    bool flag = 1;
                    for (int j = 1; j <= tot; j++)
                        if (s[i - 1 + j] != s1[j]) {
                            flag = 0;
                            break;
                        }
                    if (flag)
                        f2[i] = (f2[i] + f2[i + tot]) % mod;
                }
            }
        }
        int ans = 0;
        for (int i = 1,j = 0; i <= n; i++) {
            for (; j > 0 && we[j + 1] != s[i]; j = nxt[j]);
            if (we[j + 1] == s[i])
                j++;
            if (j == m1)
                ans = (ans + (long long)f1[i - m1] * f2[i + 1] % mod) % mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}