2020-2021:teams:legal_string:王智彪:后缀自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:王智彪:后缀自动机 [2021/07/30 16:08] 王智彪 |
2020-2021:teams:legal_string:王智彪:后缀自动机 [2021/07/30 17:04] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 229: | 行 229: | ||
| </hidden> | </hidden> | ||
| + | |||
| + | 8.最长公共子串 | ||
| + | |||
| + | 后缀数组基本操作。 | ||
| + | |||
| + | 后缀自动机做法：对 $S$ 构造后缀自动机，处理字符串 $T$ ，对于每一个前缀，都在 $S$ 中寻找这个前缀的最长后缀。显然所有这样的答案取最大值就是最终的答案了。 | ||
| + | |||
| + | 我们维护两个变量：当前状态 $v$ 和当前长度 $l$ 。最开始 $v=t_{0}$ 且 $l=0$ 。 | ||
| + | |||
| + | 如果存在从 $v$ 到字符 $c$ 的转移，我们只需要转移并且让 $l++$ 。 | ||
| + | |||
| + | 如果不存在只能让状态一直跳 $link$ ，并且缩短长度，赋值为当前状态的长度 $len(v)$ 即可。 | ||
| + | |||
| + | 如果仍不存在，则必然到达 $-1$ ，这时我们重新让 $v=0,l=0$ 。 | ||
| + | |||
| + | 这样我们最多移动两倍 $|T|$ ，所以时间复杂度就是 $O(|T|)$ 。 | ||
| + | |||
| + | <hidden 实现> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | void work_lcs(char s1[],char s2[]) { | ||
| + | ans=0,anspos=-1; | ||
| + | int l1=strlen(s1),l2=strlen(s2); | ||
| + | for(int i=0;i<l1;i++) { | ||
| + | add(s1[i]-'a',i+1); | ||
| + | } | ||
| + | int v=1,l=0; | ||
| + | for(int i=0;i<l2;i++) { | ||
| + | while(v!=1&&!dian[v].ch[s2[i]-'a']) { | ||
| + | v=dian[v].fa; | ||
| + | l=dian[v].len; | ||
| + | } | ||
| + | if(dian[v].ch[s2[i]-'a']) { | ||
| + | v=dian[v].ch[s2[i]-'a']; | ||
| + | l++; | ||
| + | } | ||
| + | if(l>ans) { | ||
| + | ans=l; | ||
| + | anspos=i; | ||
| + | } | ||
| + | } | ||
| + | //printf("%d %d\n",ans,anspos); | ||
| + | if(anspos==-1) { | ||
| + | puts("no lcs!"); | ||
| + | } | ||
| + | else { | ||
| + | for(int i=anspos-ans+1;i<=anspos;i++) { | ||
| + | putchar(s2[i]); | ||
| + | } | ||
| + | putchar(10); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | 剩下在oi-wiki上的例题之后再补吧... | ||
2020-2021/teams/legal_string/王智彪/后缀自动机.1627632503.txt.gz · 最后更改: 2021/07/30 16:08 由 王智彪
