Codechef CLHMSG Hidden Message KMP+动态规划

栏目: 编程工具 · 发布时间: 6年前

内容简介:将\(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)\)。

将\(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;
}

以上所述就是小编给大家介绍的《Codechef CLHMSG Hidden Message KMP+动态规划》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Web前端黑客技术揭秘

Web前端黑客技术揭秘

钟晨鸣、徐少培 / 电子工业出版社 / 2013-1 / 59.00元

Web前端的黑客攻防技术是一门非常新颖且有趣的黑客技术,主要包含Web前端安全的跨站脚本(XSS)、跨站请求伪造(CSRF)、界面操作劫持这三大类,涉及的知识点涵盖信任与信任关系、Cookie安全、Flash安全、DOM渲染、字符集、跨域、原生态攻击、高级钓鱼、蠕虫思想等,这些都是研究前端安全的人必备的知识点。本书作者深入剖析了许多经典的攻防技巧,并给出了许多独到的安全见解。 本书适合前端工......一起来看看 《Web前端黑客技术揭秘》 这本书的介绍吧!

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具