后缀自动机SuffixAutomaton.ppt

后缀自动机Suffix Automaton
杭州外国语学校陈立杰
WJMZBMR
吐槽&回答
Q:你是哪里的弱菜?我听都没听说过!
A:我是来自杭州外国语学校的陈立杰,确实是弱菜。
Q:Suffix Automaton?我根本就没有听说过这种数据结构。
A:这个还是有点用处的,等下我会讲的,你就当长知识了吧。
Q:呼噜噜~~~~~~
A:睡好。。。
先让我们看SPOJ上的一道题目
1812. mon Substring II
题目大意:给出N(N <= 10)个长度不超过100000的字符串,求他们的最长公共连续子串。
时限:SPOJ上的2s
一个简单的做法
二分答案之后使用哈希就可以在O(LlogL)的时间内解决这个问题。这个做法非常经典就不详细讲了。
看起来很简单。。但是。。。
我们可以看到大部分人都TLE了。。为什么呢?
SPOJ太慢了
SPOJ太慢了
SPOJ太慢了
SPOJ太慢了
SPOJ太慢了
SPOJ太慢了
SPOJ太慢了
新的算法
OI中使用的字符串处理工具
Suffix Array 后缀数组
Suffix Tree 后缀树
Aho-Corasick Automaton AC自动机
Hash 哈希
Suffix Automaton又是什么呢?
什么是自动机
有限状态自动机的功能是识别字符串,令一个自动机A,若它能识别字符串S,就记为A(S)=True,否则A(S)=False。
自动机由五个部分组成,alpha:字符集,state:状态集合,init:初始状态,end:结束状态集合,trans:状态转移函数。
不妨令trans(s,ch)表示当前状态是s,在读入字符ch之后,所到达的状态。
如果trans(s,ch)这个转移不存在,为了方便,不妨设其为null,同时null只能转移到null。
null表示不存在的状态。
同时令trans(s,str)表示当前状态是s,在读入字符串str之后,所到达的状态。
trans(s,str)
Cur = s;
For i = 0 to Length(str)-1
Cur = trans(Cur,str[i]);trans(s,str) 就是Cur