hihoCoder 后缀数组重复旋律

2023-08-23 14:27:10

#1403 : 后缀数组一·重复旋律

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。

小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列，相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。

小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少？

解题方法提示

输入

第一行两个整数 N和K。1≤N≤20000 1≤K≤N

接下来有 N 个整数，表示每个音的数字。1≤数字≤100

输出

一行一个整数，表示答案。

样例输入

样例输出

先求出后缀数组，问题转换为询问height数组中连续k-1个数的最小值的最大值，单调队列扫描一遍即可。

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #define siz 1024

 inline int get_c(void)

 {

     static char buf[siz];

     static char *head = buf + siz;

     static char *tail = buf + siz;

     if (head == tail)

         fread(head = buf, , siz, stdin);

     return *head++;

 }

 inline int get_i(void)

 {

     register int ret = ;

     register int neg = false;

     register int bit = get_c();

     for (; bit < ; bit = get_c())

         if (bit == '-')neg ^= ;

     for (; bit > ; bit = get_c())

         ret = ret *  + bit - ;

     return neg ? -ret : ret;

 }

 #define N 20005

 int n, m, s[N];

 int A[N], cntA[N];

 int B[N], cntB[N];

 int sa[N], rk[N], ht[N], tsa[N];

 int que[N], hd, tl, answer;

 signed main(void)

 {

     n = get_i();

     m = get_i();

     for (int i = ; i <= n; ++i)

         s[i] = get_i();

     memset(cntA, , sizeof(cntA));

     for (int i = ; i <= n; ++i)

         ++cntA[s[i]];

     for (int i = ; i <= ; ++i)

         cntA[i] += cntA[i - ];

     for (int i = n; i >= ; --i)

         sa[cntA[s[i]]--] = i;

     rk[sa[]] = ;

     for (int i = ; i <= n; ++i)

         rk[sa[i]] = rk[sa[i - ]] + (s[sa[i]] != s[sa[i - ]]);

     for (int l = ; rk[sa[n]] < n; l <<= )

     {

         memset(cntA, , sizeof(cntA));

         memset(cntB, , sizeof(cntB));

         for (int i = ; i <= n; ++i)

         {

             ++cntA[A[i] = rk[i]];

             ++cntB[B[i] = i + l <= n ? rk[i + l] : ];

         }

         for (int i = ; i <= n; ++i)

             cntB[i] += cntB[i - ];

         for (int i = ; i <= n; ++i)

             cntA[i] += cntA[i - ];

         for (int i = n; i >= ; --i)

             tsa[cntB[B[i]]--] = i;

         for (int i = n; i >= ; --i)

             sa[cntA[A[tsa[i]]]--] = tsa[i];

         rk[sa[]] = ;

         for (int i = ; i <= n; ++i)

             rk[sa[i]] = rk[sa[i - ]] + (A[sa[i]] != A[sa[i - ]] || B[sa[i]] != B[sa[i - ]]);

     }

     for (int i = , j = ; i <= n; ++i)

     {

         j = j ? j -  : ;

         while (s[i + j] == s[sa[rk[i] - ] + j])++j;

         ht[rk[i]] = j;

     }

     for (int i = ; i < m; ++i)

     {

         while (tl != hd && ht[i] < ht[que[tl]])

             --tl;

         que[++tl] = i;

     }

     answer = ht[que[hd]];

     for (int i = m; i <= n; ++i)

     {

         while (tl != hd && ht[i] < ht[que[tl]])

             --tl;

         que[++tl] = i;

         while (hd != tl && que[hd + ] <= i - m + )

             ++hd;

         if (answer < ht[que[hd + ]])

             answer = ht[que[hd + ]];

     }

     printf("%d\n", answer);

 }

#1407 : 后缀数组二·重复旋律2

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。

旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？

解题方法提示

输入

第一行一个整数 N。1≤N≤100000

接下来有 N 个整数，表示每个音的数字。1≤数字≤1000

输出

一行一个整数，表示答案。

样例输入

8

1 2 3 2 3 2 3 1

样例输出

二分答案，转换为判断是否存在长度>=k的不重叠的两个子串。判定两个后缀是否重叠，只需要看abs(st1-st2)和k的大小关系即可，所以找出极长的连续的大于等于k的一段height，维护其中的st的最大和最小值，即可判断是否存在合法的两个子串。

 #include <bits/stdc++.h>

 #define siz 1024

 inline int get_c(void)

 {

     static char buf[siz];

     static char *head = buf + siz;

     static char *tail = buf + siz;

     if (head == tail)

         fread(head = buf, , siz, stdin);

     return *head++;

 }

 inline int get_i(void)

 {

     register int ret = ;

     register int neg = false;

     register int bit = get_c();

     for (; bit < ; bit = get_c())

         if (bit == '-')neg ^= true;

     for (; bit > ; bit = get_c())

         ret = ret *  + bit - ;

     return neg ? -ret : ret;

 }

 #define N 100005

 const int inf = 2e9 + ;

 int n, s[N];

 int A[N], cntA[N];

 int B[N], cntB[N];

 int sa[N], rk[N], ht[N], ta[N];

 inline bool check(int k)

 {

     int max = sa[], min = sa[];

     for (int i = ; i <= n; ++i)

     {

         if (ht[i] >= k)

         {

             if (max < sa[i])

                 max = sa[i];

             if (min > sa[i])

                 min = sa[i];

             if (min + k <= max)

                 return true;

         }

         else

             max = min = sa[i];

     }

     return false;

 }

 signed main(void)

 {

     n = get_i();

     for (int i = ; i <= n; ++i)

         s[i] = get_i();

     memset(cntA, , sizeof(cntA));

     for (int i = ; i <= n; ++i)

         ++cntA[s[i]];

     for (int i = ; i <= ; ++i)

         cntA[i] += cntA[i - ];

     for (int i = n; i >= ; --i)

         sa[cntA[s[i]]--] = i;

     rk[sa[]] = ;

     for (int i = ; i <= n; ++i)

         rk[sa[i]] = rk[sa[i - ]] + (s[sa[i]] != s[sa[i - ]]);

     for (int l = ; rk[sa[n]] < n; l <<= )

     {

         memset(cntA, , sizeof(cntA));

         memset(cntB, , sizeof(cntB));

         for (int i = ; i <= n; ++i)

         {

             ++cntA[A[i] = rk[i]];

             ++cntB[B[i] = i + l <= n ? rk[i + l] : ];

         }

         for (int i = ; i <= n; ++i)

             cntA[i] += cntA[i - ];

         for (int i = ; i <= n; ++i)

             cntB[i] += cntB[i - ];

         for (int i = n; i >= ; --i)

             ta[cntB[B[i]]--] = i;

         for (int i = n; i >= ; --i)

             sa[cntA[A[ta[i]]]--] = ta[i];

         rk[sa[]] = ;

         for (int i = ; i <= n; ++i)

             rk[sa[i]] = rk[sa[i - ]] + (A[sa[i]] != A[sa[i - ]] || B[sa[i]] != B[sa[i - ]]);

     }

     for (int i = , j = ; i <= n; ++i)

     {

         if (--j < )j = ;

         while (s[i + j] == s[sa[rk[i] - ] + j])++j;

         ht[rk[i]] = j;

     }

     int lt = , rt = n, mid, ans = ;

     while (lt <= rt)

     {

         mid = (lt + rt) >> ;

         if (check(mid))

             ans = mid, lt = mid + ;

         else

             rt = mid - ;

     }

     printf("%d\n", ans);

 }

#1415 : 后缀数组三·重复旋律3

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。

旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？

解题方法提示

输入

共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

输出

一行一个整数，表示答案。

样例输入

abcdefg

abacabca

样例输出

把两个串接在一起跑后缀数组，找出最大的height使得两个后缀从不同串开始即可。

 #include <bits/stdc++.h>

 #define N 200005

 int n;

 int m;

 int len;

 int cut;

 int s[N];

 int sa[N];

 int rk[N];

 int ta[N];

 int ht[N];

 int A[N], cntA[N];

 int B[N], cntB[N];

 char s1[N];

 char s2[N];

 signed main(void)

 {

     scanf("%s", s1 + );

     scanf("%s", s2 + );

     n = strlen(s1 + );

     m = strlen(s2 + );

     for (int i = ; i <= n; ++i)

         s[++len] = s1[i] - 'a' + ;

     s[cut = ++len] = ;

     for (int i = ; i <= m; ++i)

         s[++len] = s2[i] - 'a' + ;

     s[++len] = ;

     memset(cntA, , sizeof(cntA));

     for (int i = ; i <= len; ++i)

         ++cntA[s[i]];

     for (int i = ; i <= ; ++i)

         cntA[i] += cntA[i - ];

     for (int i = len; i >= ; --i)

         sa[cntA[s[i]]--] = i;

     rk[sa[]] = ;

     for (int i = ; i <= len; ++i)

         rk[sa[i]] = rk[sa[i - ]] + (s[sa[i]] != s[sa[i - ]]);

     for (int l = ; rk[sa[len]] < len; l <<= )

     {

         memset(cntA, , sizeof(cntA));

         memset(cntB, , sizeof(cntB));

         for (int i = ; i <= len; ++i)

         {

             ++cntA[A[i] = rk[i]];

             ++cntB[B[i] = i + l <= len ? rk[i + l] : ];

         }

         for (int i = ; i <= len; ++i)

             cntA[i] += cntA[i - ],

             cntB[i] += cntB[i - ];

         for (int i = len; i >= ; --i)

             ta[cntB[B[i]]--] = i;

         for (int i = len; i >= ; --i)

             sa[cntA[A[ta[i]]]--] = ta[i];

         rk[sa[]] = ;

         for (int i = ; i <= len; ++i)

             rk[sa[i]] = rk[sa[i - ]] + (

                 A[sa[i]] != A[sa[i - ]]

             ||    B[sa[i]] != B[sa[i - ]]);

     }

     for (int i = , j = ; i <= len; ++i)

     {

         if (--j < )j = ;

         while (s[i + j] == s[sa[rk[i] - ] + j])++j;

         ht[rk[i]] = j;

     }

     int ans = ;

     for (int i = ; i <= len; ++i)

         if ((sa[i] < cut) != (sa[i - ] < cut))

             ans = std::max(ans, ht[i]);

     printf("%d\n", ans);

 }

#1419 : 后缀数组四·重复旋律4

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。

我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。

小Hi想知道一部作品中k最大的(k,l)-重复旋律。

解题方法提示

输入

一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

输出

一行一个整数，表示答案k。

样例输入

babbabaabaabaabab

样例输出

这道题有点复杂…… 好在HiHo的提示很好。

小Ho：这一次的问题该如何解决呢？

小Hi：嗯，这次的问题是重复次数最多的连续字串。

小Ho：似乎不好下手啊。

小Hi：那我们先降低难度，不如考虑如何解决如何求一个串的最大重复次数。

小Ho：嗯。我想想，比如说串abababab，既可以是(1,8)，也可以是(2,4)，最大的是(4,2)。

小Hi：对。假如说我们枚举一个可能的循环节长度l（或者k），能不能快速判断这个l是否合法呢？

小Ho：啊！我想想...似乎是求原串和原串去掉前l个字符后两个串的LCP（最长公共前缀），如果能完全匹配上，就满足！

小Hi：对，没错。比如abababab，检验是否是(2,4)，就拿abababab和ababab求LCP。

小Hi：值得一提的是，利用height数组可以快速求出我们需要的LCP。例如abababab的height数组如下：

suffix	sa	height
ab	7	0
abab	5	2
ababab	3	4
abababab	1	6
b	8	0
bab	6	1
babab	4	3
bababab	2	5

小Hi：如果我们要求某两个后缀的LCP，只要求它们中间的一段height数组的最小值即可。例如abababab和ababab的LCP就是[4]这段的最小值，即2；bab和bababab的LCP就是[3, 5]这段的最小值，即3；ab和babab的LCP就是[2, 4, 6, 0, 1, 3]这段的最小值，即0。

小Hi：这个求height数组某一段最小值的问题，恰好是之前讲过的[RMQ问题]，可以通过O(NlogN)的预处理达到O(1),处理单次询问；当然使用线段树等数据结构也是可以的，单次询问O(logN)。

小Ho：明白了。回到原问题，那我们肯定是要先枚举(k,l)中的这个l，再枚举起始位置i，计算Suffix(i)和Suffix(i+l)的LCP，记作lcp(l, i)，那么k(l, i)就等于lcp(l,i)/l + 1。对于所有的循环节长度l和起始位置i，最大的k(l, i)就是答案。

小Hi：你说的对！不过本题还是有进一步优化的空间。对于确定的l，我们不用枚举所有的起始位置i，而只枚举i是l的整数倍的情况。如果最优串的开始位置恰好在l的倍数上，那我们找到的最大的k就是正确答案。

小Ho：道理是这么个道理。不过如果最优串的开始位置不在l的倍数上呢？

小Hi：即使不是，问题也会太糟糕，假如说最优串位置在x，可以想象我们会枚举到x之后的一个最近位置p，p是l的倍数。并且我们计算出了Suffix(p)和Suffix(p+l)的LCP，lcp(l, p)那么此时的k(l, p)=lcp(l, p)/l+1。

小Hi：对于被我们略过的k(l, p-1), k(l, p-2) ... k(l, p-l+1)，它们的上限是k(l, p)+1。

小Ho：没错。因为它们的起始位置距离p不超过l，所以最多比Suffix(p)增加一个循环节。

小Hi：其次，如果k(l, p-1), k(l, p-2) ... k(l, p-l+1)中有一个的值是k(l, p)+1的话，那么k(l, p - l + lcp(l, p) mod l)一定等于k(l, p)+1。(mod是取余运算)

小HO：为什么呢？

小Hi：举个例子，比如串XaYcdabcdabcd(XY各代表一个不确定的字符，具体代表的字符会影响最后答案，我们后面会分析到)，当我们考虑l=4的时候，第一次枚举p=4的起始位置，会求出cdabcdabcd和cdabcd的lcp(4, 4)=6，k(4, 4)=2。根据上面的论断，只有当k(l, p - l + lcp(l, p) mod l)=k(4, 4 - 4 + 6 mod 4)=k(4, 2)=3时，k(4, 1), k(4, 2)和k(4, 3)中才会有3。首先我们可以判断k(4, 3)一定不可能等于3，因为无论Y是哪个字符，Ycdabcdabcd和bcdabcd的LCP即lcp(4, 3)最大是7，不到8。其次如果k(4, 2) ≠ 3，那么k(4, 1)也没戏。因为如果k(4, 2) ≠ 3，说明aY和ab匹配不上，这时无论X是哪个字符，XaY和dab匹配不上，lcp(4, 1) < l，k(4, 1) = 1。

小Ho：哦，我有点明白了。k(l, p - l + lcp(l, p) mod l)是一个分界线，右边的值因为LCP不够大，一定不能增加一个循环节。并且如果k(l, p - l + lcp(l, p) mod l)没有增加循环节的话，说明[p - l + lcp(l, p) mod l, p]这段中间匹配出错，左边的lcp也跟着雪崩，更不可能增加循环节了。

小Hi：没错！

小Ho：那枚举l和枚举开始位置的时间复杂度呢？

小Hi：你会发现，枚举完l后枚举开始位置的时间复杂度是O(n/l)的，所以总复杂度是O(n/1)+O(n/2)+O(n/3)...这个是一个经典的求和，总复杂度是O(nlogn)的。

小Ho：明白了！好神奇，看似简单朴素的想法，复杂度却也很低。

小Hi：是啊。以下是二分判断的C++代码实现：

for(L＝1;L <= n;L++)

{

    for (int i = 1; i + L <= n; i += L)

    {

        int R = lcp(i, i + L);

        ans = max(ans, R / L + 1);

        if (i >= L - R % L)

        {

            ans = max(lcp(i - L + R%L, i + R%L) / L + 1, ans);

        }

    }

}

小Ho：好的。我这就实现一下。

然后我就实现了一下…… 对于证明一脸懵逼……

 #include <bits/stdc++.h>

 #define N 100005

 int n; char s[N];

 int A[N], cntA[N];

 int B[N], cntB[N];

 int sa[N], rk[N], ht[N], ta[N];

 int tr[N << ];

 void build(int t, int l, int r)

 {

     if (l == r)

         tr[t] = ht[l];

     else

     {

         int mid = (l + r) >> ;

         build(t << , l, mid);

         build(t <<  | , mid + , r);

         tr[t] = std::min(

             tr[t << ],

             tr[t <<  | ]

         );

     }

 }

 int query(int t, int l, int r, int a, int b)

 {

     if (l == a && r == b)

         return tr[t];

     int mid = (l + r) >> ;

     if (b <= mid)

         return query(t << , l, mid, a, b);

     else if (a > mid)

         return query(t <<  | , mid + , r, a, b);

     else

         return std::min(

             query(t << , l, mid, a, mid),

             query(t <<  | , mid + , r, mid + , b)

         );

 }

 inline int lcp(int a, int b)

 {

     a = rk[a];

     b = rk[b];

     if (a > b)

         std::swap(a, b);

     return query(, , n, a + , b);

 }

 signed main(void)

 {

     scanf("%s", s + ); n = strlen(s + );

     memset(cntA, , sizeof(cntA));

     for (int i = ; i <= n; ++i)

         ++cntA[s[i]];

     for (int i = ; i <= ; ++i)

         cntA[i] += cntA[i - ];

     for (int i = n; i >= ; --i)

         sa[cntA[s[i]]--] = i;

     rk[sa[]] = ;

     for (int i = ; i <= n; ++i)

         rk[sa[i]] = rk[sa[i - ]] + (s[sa[i]] != s[sa[i - ]]);

     for (int l = ; rk[sa[n]] < n; l <<= )

     {

         memset(cntA, , sizeof(cntA));

         memset(cntB, , sizeof(cntB));

         for (int i = ; i <= n; ++i)

         {

             ++cntA[A[i] = rk[i]];

             ++cntB[B[i] = i + l <= n ? rk[i + l] : ];

         }

         for (int i = ; i <= n; ++i)

             cntA[i] += cntA[i - ],

             cntB[i] += cntB[i - ];

         for (int i = n; i >= ; --i)

             ta[cntB[B[i]]--] = i;

         for (int i = n; i >= ; --i)

             sa[cntA[A[ta[i]]]--] = ta[i];

         rk[sa[]] = ;

         for (int i = ; i <= n; ++i)

             rk[sa[i]] = rk[sa[i - ]] + (A[sa[i]] != A[sa[i - ]] || B[sa[i]] != B[sa[i - ]]);

     }

     for (int i = , j = ; i <= n; ++i)

     {

         if (--j < )j = ;

         while (s[i + j] == s[sa[rk[i] - ] + j])++j;

         ht[rk[i]] = j;

     }

     build(, , n);    

     int ans = ;

     for (int L = ; L <= n; ++L)

     {

         for (int i = ; i + L <= n; i += L)

         {

             int R = lcp(i, i + L);

             ans = std::max(ans, R/L + );

             if (i >= L - R % L)

                 ans = std::max(ans,

                     lcp(i-L+R%L,i+R%L)/L+);

         }

     }

     printf("%d\n", ans);

 }

@Author: YouSiki

码农公寓

#1403 : 后缀数组一·重复旋律

描述

输入

输出

#1407 : 后缀数组二·重复旋律2

描述

输入

输出

#1415 : 后缀数组三·重复旋律3

描述

输入

输出

#1419 : 后缀数组四·重复旋律4

描述

输入

输出

相关文章