我在站军姿的时候热的不行。。只好瞎想分散注意力囧。。。莫名其妙想到了这么一个SB算法。。
多串匹配，就是有N个串，问模板串里面有没有其中一个串。。
假设模板串长度为T。。那么N次KMP显然需要至少NT的时间，不是很理想。。
然后有一个很NB的Aho-Corasick算法。。可是我过于沙茶完全不会。。。
然后就想到一个非常沙茶的算法，具体说就是先对所有串进行new lcp的预处理。。
然后把模板串的SA求出来，
然后用二分查找的办法找出跟当前串匹配长度最长的后缀，再进行检查。。
分析以下复杂度囧。。。new lcp TLogT，SA TLogT，二分查找（每次检查都是LogT的）LogT^2
总共就是TLogT+N*LogT^2…勉强能过某道多串匹配的题目囧。。。。
ooooooooooooooorz
MS，2009国家队后缀数组，里有讲二分做多模式匹配的
回复ahhygx：Orz神牛！！！！恩。。这个是二分做多串匹配囧。。那个完全没用Hash不是很一样的囧。。
hdu 2222，我以前用上面方法写了，模板串n<=100w，但MLE，RMQ超内存了，只好用AC自动机了。。
回复macrus：Orz神牛！！！！！！！！！！我是沙茶。。。
ac自动机巨简单啊（比后缀树好写多了）
回复中国脑筋：我巨傻叉阿。。。完全不懂。。。
JSOI以前就经常考AC自动机，结果我不会；学了AC自动机后，又不考了- -!
请问你有用Suffix Automaton过SPOJ的SUBLEX吗？我遇到了很大的麻烦。。。如果你曾经过了，请求帮忙！。。。联系：fanhqme@126.com