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