双通网络网站建设价格,dede移动端网站源码,做网站项目团队口号,硅谷网站开发薪酬今天对字符串有了一点新的理解#xff0c;遂再写一篇博客。
字符串取模
定义
可以参考 我之前写的博客。不再赘述。下文用长度表示。
运算 ( S c ) ≡ ( S m o d P ) c ( m o d P ) (Sc) \equiv (S \bmod P) c \pmod P (Sc)≡(SmodP)c(modP)
KMP
定义 g o ( i , c )…今天对字符串有了一点新的理解遂再写一篇博客。
字符串取模
定义
可以参考 我之前写的博客。不再赘述。下文用长度表示。
运算 ( S c ) ≡ ( S m o d P ) c ( m o d P ) (Sc) \equiv (S \bmod P) c \pmod P (Sc)≡(SmodP)c(modP)
KMP
定义 g o ( i , c ) go(i, c) go(i,c) 函数表示 P P P 的 i i i 前缀添加字符 c c c 的字符串的模 P P P 值。定义失配函数fail f i f_i fi 表示 P P P 的 i i i 前缀时增加的字符 c c c 失配的模 P P P 值。 g o ( i , c ) { i 1 P i c g o ( f i , c ) P i ≠ c go(i, c) \begin{cases} i1 P_i c\\ go(f_i,c) P_i \ne c \end{cases} go(i,c){i1go(fi,c)PicPic
int go(int i, char c)
{if(P[i] c) return i 1;if(i 0) return 0;return go(f[i], c);
}...for(int i0; iP.size(); i)f[i1] go(f[i], c); // 这里 fail 数组分析
关于 f i f_i fi一方面从自动机角度考虑即 π i \pi_i πi。
一方面从字符串取模的角度考虑 f i P [ 1.. i ) f_iP[1..i) fiP[1..i) 模 P P P 值。那么 P [ 0... f i ) ≡ P [ 1... i ) ( m o d P ) P[0...f_i) \equiv P[1...i) \pmod P P[0...fi)≡P[1...i)(modP)发现 f i f_i fi 同样满足 π i \pi_i πi 的性质。
复杂度分析
对于一般的 KMP 问题设文本串长 n n n模式串长 m m m。
int cur 0;
for(int i0; itext.size(); i)
{cur go(cur, text[i]);...
}首先有 f i i f_i i fii。文本字符可能提供当前字符串模 P P P 后的长度至多增加 n n n 次。因此复杂度是线性的。 无限猴子类技巧
问题形如出现某个模式串 P P P 的期望长度。
由于只关心匹配考虑只关心模 P P P 的值据此结合待定系数法做期望 dp 即可。
例题
Censoring S
无限猴子
[CTSC2006] 歌唱王国 清除模式类技巧
如题清除字符串中的模式串 P P P。
逐位枚举考虑当前字符串模 P P P 的值即可。
例题
清除模式
Pareidolia G
