字符串

魔改 KMP 大概是不行的，卷积在这里出现的很妙。 卷积处理匹配 定义匹配函数 $$ d(x,y) = [x = y] $$ 给定文本串 $B$ 和长为 $m$ 的模式串 $A$，要找出 $A$ 在 $B$ 的所有出现，可以定义 $$ f(k) = \sum_{i=0}^{m-1} d(A_{i}, B_{i-m+k}) $$ 即 $f(k) = 0$ 时有完全匹配 $A = B[k-m\ldots k-1]$。考虑让 $d$ 函数更 “数学” 一点，以更好的计算 $$ d(x,y) = (x - y)^2 $$ 再提供模式串 $A$ 的翻转 $S$，即 $A_i = S_{m-i}$，展开有 $$ \begin{aligned} f(k) &= \sum_{i=0}^{m-1}A_{i}^2 + \sum_{i=0}^{m-1}B_{i-m+k}^2 - 2\sum_{i=0}^{m-1} A_{i}B_{i-m+k}\\ &= \sum_{i=0}^{m-1}A_{i}^2 + \sum_{i=0}^{m-1}B_{i-m+k}^2 - 2\sum_{i=0}^{m-1} S_{m-i}B_{i-m+k} \end{aligned} $$...

题目大意 我们将重复的 $n$ 个字符串 S 压缩为 [nS]，且存在多重压缩。给定一个压缩结果，展开它。 分析 我考虑用类似状态机的方式解析字符串。 当读到正常字符时，把它添到 $s$ 末尾 读到左括号时，则递归 read()，重复 $n$ 遍添到 $s$ 末尾 右括号或文本结束则返回 $s$ 写成 BNF 更直观一点 <pwd> ::= <EMPTY> | {<ALPHA>} | <pwd> "[" <NUMBER> <pwd> "]" <pwd> string read() { string s = ""; char c; while (cin >> c) { if (c == '[') { int n; cin >> n; string ts = read(); while (n--) s += ts; } else if (c == ']') { return s; } else { s += c; } } return s; } int main() { cout << read(); return 0; }