首页 > web前端 > html教程 > Codeforces Round #244 (Div. 2)D (后缀自动机)_html/css_WEB-ITnose

Codeforces Round #244 (Div. 2)D (后缀自动机)_html/css_WEB-ITnose

WBOY
发布: 2016-06-24 12:05:08
原创
997 人浏览过

Codeforces Round #244 (Div. 2)D (后缀自动机)

(标号为0的节点一定是null节点,无论如何都不能拿来用,切记切记,以后不能再错了)

这题用后缀自动机的话,对后缀自动机的很多性质有足够深刻的理解。没想过后缀数组怎么做,因为不高兴敲。。。。

题意:给出两个长度均不超过5000的字符串s1,s2,求这两个串中,都只出现一次的最短公共子串。

解题思路:求的是公共子串,然后对出现的次数又有限制,第一想法就是后缀自动机啊,后缀自动机处理子串出现次数再合适不过了。做法是这样的,先建立s1的sam,用拓扑dp,求出每个节点的代表串出现的次数。目的是什么呢?其实我是想求ok[i][j],表示s1[i] ~ s1[j]的这个子串是否只出现了一次。现在我们求出了代表串的出现次数了,怎么求这个ok[i][j]呢?拿s1在建立好的自动机上匹配,当前匹配到了s1[i],记录temp表示当前匹配的最长长度,now表示当前匹配在哪个节点。这里有一个跟AC自动机很相似的性质,匹配到了now,则一定能匹配fa[now]。那么就顺着now往上走,一直找到第一个出现次数大于1的节点p,那么以i为结尾,长度为val[p]+1到temp的子串在s1里面肯定都只出现一次了。把这个记录到ok数组里。    第二步是对s2处理了,还是一样的过程,建立sam,求出每个点的代表串出现的次数,即cnt[]数组。   第三步就要拿s1在s2的sam上进行匹配了,匹配过程类似于前面处理s1的ok数组,找出当前匹配的最长长度temp,匹配到的节点now,顺着now往上,找到第一个cnt大于1的节点p,在s2里面,以当前匹配上的子串的结尾为结尾的长度为val[p] + 1到temp的子,串必然只在s2里出现过一次。然后就枚举j,从val[p] + 1到temp,如果在s1里面,以i为结尾,长度为j的子串只出现1次(即ok[i-j+1][i] == 1),那么这个j就有可能成为答案,用其更新ans即可。

代码:

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std ;const int maxn = 5001 ;bool ok[maxn][maxn] ;int ans = 111111 ;struct SAM  {    int fa[maxn= 1 ; i -- ) {            now = ws[i] ;            cnt[fa[now]] += cnt[now] ;        }    }    void gao ( char *s , int n ) {        get_cnt ( s , n ) ;        int now = 1 , i , j ;        for ( i = 1 ; i   <br>  <br>  <p></p> </algorithm></string.h></stdio.h>
登录后复制
相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板