AC 自动机(Aho–Corasick 算法)与字符串匹配问题(HDU 2222 Keywords Search)

据说很多公司都有这样一道面试题:给你几个 G 的字符串,让你想办法快速地找出其中的很多个需要和谐的敏感词。
这个问题里,如果“需要和谐的字符串”称为“模式串”,“待被查的字符串”称为文本串。对于这样的问题,如果暴力做,复杂度就是 \Theta(N \ast M \ast Len)……用 AC 自动机这种高级的算法,可以在 \Theta (N) 左右复杂度内得出答案。Excited!

差分约束系统(System of Difference Constraints)的应用(POJ 1201 Intervals,POJ 3159 Candies)

如果告诉你在一个三角形中,B-A \leqslant c, C-B \leqslant a, C-A \leqslant b,怎么求 C-A 的最大值呢?通过yy观察可以发现,C-A 的最大值是 min(a+c,b)。这个答案如何得出?将这个三角形内的约束条件推广到更多约束条件呢?

网络流最大流算法总结(Edmonds-Karp 算法+Dinic 算法)

“网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关。网络流的理论和应用在不断发展,出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。”
——百度百科

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。