分类目录归档:公告

KMP算法&AC自动机小记

KMP算法

考虑匹配A串和B串,在A串里去寻找B串。

暴力的匹配方法是O(n^{2})的,我们发现如果每次都去从头开始,那未免太费力不讨好了。

我们能否利用已有信息进行一点优化呢?答案是肯定的。

考虑我们A串匹配到iB串匹配到j,那么有A[i]=B[j],A[i+1]\neq B[j+1]

继续阅读

我的模板

图论部分

Tarjan求割点数

继续阅读