2020-2021:teams:legal_string:王智彪:后缀数组
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:后缀数组 [2021/07/26 21:13] 王智彪 |
2020-2021:teams:legal_string:王智彪:后缀数组 [2021/07/28 15:53] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 377: | 行 377: | ||
| </hidden> | </hidden> | ||
| + | |||
| + | 5.后缀数组还可以解决连续重复子串的问题 | ||
| + | |||
| + | 我们规定连续重复串为：某一个字符串 $L$ 是由某个字符串 $S$ 重复 $R$ 次得到的，则称 $L$ 是一个连续重复串， $R$ 是这个字符串的重复次数。 | ||
| + | |||
| + | 5.1求连续重复子串出现次数最大值 | ||
| + | |||
| + | 首先肯定要枚举长度 $k$ ，判断 $k$ 是否整除总长度，然后只需要比较 $lcp(rk[1],rk[k+1])$ 是否是 $n-k$ 就可以了。因为前提是整除，然后 $lcp(rk[1],rk[k+1])$ 是下标为 $1$ 的串和下标为 $k+1$ 的串的相同前缀，如果把 $k+1$ 的剩下都包括了就可以说明每 $k$ 个都一样，画个图就知道了。于是还需要枚举最小的长度就可以了，求出 $height$ 之后复杂度是 $O(n)$ 的。 | ||
| + | |||
| + | 5.2求一个字符串的所有子串中重复次数最多的连续重复子串 | ||
| + | |||
| + | 先穷举长度 $L$ ，然后看所有的长度为 $L$ 的子串最多能连续出现几次。出现一次就是这个串本身，我们直接考虑两次及以上的情况，注意如果子串出现了至少两次，我们取这些字符 $s[1],s[L+1],s[2*L+1]…$ ，这些字符中一定会有两个出现在这个大串中，其实我们只需要将这些字符代表的相邻后缀取一下 $lcp$ 就行，比如现在有一个串是 $habcabcabcabxyz$ ，然后这个最大显然是 $cabcabcabxyz$ 和 $cabcabxyz$ ，这个的 $lcp$ 长度是 $6$ ，然后查一下实际上是 $3$ 个，也就是 ${\frac 6 3}+1$ 。但是这并不一定正确，因为比如现在串删了一个字符，变成了 $habcabcabcaxyz$ 。现在长度为 $5$ ，但事实上还是应该是 $3$ ，原因很简单，我们并没有将所有的情况都讨论进去，只是每隔这个长度找一下，导致有的串被切成两个段了，次数会少算 $1$ ，这个很直观地可以看出来可以向前移动 $5\%3=2$ 的长度，因为这些长度相当于被浪费了，然后算一下那两个新的点的 $lcp$ ，如果大于等于 $L$ ，说明刚才有一个没算进去，反之不用管，这样复杂度就是 $O(n×({\frac 1 1}+{\frac 1 2}+…+{\frac 1 n}))=O(nlogn)$ 。 | ||
| + | |||
| + | 6.出现或反转后出现在每个字符串中的最长子串 | ||
| + | |||
| + | 我们将所有字符串和他们倒过来的字符串用没出现过的字符分割并相连。然后把除了分隔符之外的每一个位置都标记好是哪个字符串中出现的。然后显然是二分答案。翻转后的字符串和翻转之前的字符串都是标记同一个字符串，一起求后缀数组，这样就可以既考虑翻转又考虑没翻转的情况了。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | bool check( int limit , int len ) { | ||
| + | memset( have , false , sizeof(have) ) ;//清空，防止受上次结果影响 | ||
| + | if( in[sa[1]] ) {//因为height数组比较的是sa[i-1]和sa[i] 所以这里先把1的放进去 | ||
| + | have[in[sa[1]]] = true ;//因为长度必然比limit大，所以一定是true | ||
| + | } | ||
| + | for( int i = 2 ; i <= len ; i ++ ) { | ||
| + | if( height[i] < limit ) { | ||
| + | int cnt = 0 ; | ||
| + | for( int j = 1 ; j <= n ; j ++ ) { | ||
| + | if( have[j] ) cnt ++ ; | ||
| + | } | ||
| + | if( cnt == n ) return true ; | ||
| + | memset( have , false , sizeof(have) ) ;//一定要把所有的清空 | ||
| + | } | ||
| + | if( in[sa[i]] ) { | ||
| + | have[in[sa[i]]] = true ;//和上面同理 | ||
| + | } | ||
| + | } | ||
| + | int cnt = 0 ; | ||
| + | for( int j = 1 ; j <= n ; j ++ ) { | ||
| + | if( have[j] ) cnt ++ ; | ||
| + | } | ||
| + | return cnt == n ;//别忘了有可能最后一步才凑够，这里要重新判断一下 | ||
| + | } | ||
| + | |||
| + | //main函数中 | ||
| + | for( int i = 1 ; i <= n; i ++ ) { | ||
| + | scanf( "%s" , str ) ; | ||
| + | int l = strlen( str ) ; | ||
| + | mm = min( mm , l ) ; | ||
| + | for( int j = 0 ; j < l ; j ++ ) {//顺着存 | ||
| + | r[len] = str[j] ; | ||
| + | in[len++] = i ; | ||
| + | } | ||
| + | r[len++] = 'z' + i ;//这里一定要区别开 | ||
| + | for( int j = l - 1 ; j >= 0 ; j -- ) {//倒着存 | ||
| + | r[len] = str[j] ; | ||
| + | in[len++] = i ; | ||
| + | } | ||
| + | r[len++] = 'z' + i + n ;//这里一定要区别开 | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | 剩下的oi-wiki上的题单待补，先爬去看别的了。 | ||
2020-2021/teams/legal_string/王智彪/后缀数组.1627305180.txt.gz · 最后更改: 2021/07/26 21:13 由 王智彪
