hihoCoder后缀数组四题

重复旋律一

1. 链接

   后缀数组一·重复旋律

2. 题意

   给一个字符串，和正整数 $ K $ ，求这个字符串中出现次数至少为 $ K $ 的串的最大长度。

3. 题解

   1. 二分答案，然后将所有后缀在以 $ Rank $ 排序时的顺序进行分组，要求每一组的 $ LCP \leq mid$。最后看是否有一组的字符串个数大于等于 $ K $即可判断该案是否成立。
   1. 使用单调队列。维护一个递增的单调队列(因为要求最小值)，并且当队头的位置和当前位置的差大于 $ K $ 时弹出队头。这样求可以快速求出任意一段长度为 $ K $ 的L后缀的 $ LCP $ 的最小值。

4. 核心代码

   for(int i=1;i<=n;i++)
   {
       while(q.size()&&height[q.back()]>=height[i]) q.pop_back();
       q.push_back(i);
       while(q.size()&&i-q.front()+1>k-1) q.pop_front();
       ans=max(ans,height[q.front()]);
   }

重复旋律二

1. 链接

   后缀数组二·重复旋律2

2. 题意

   给定一个串，求不重叠的出现次数至少为 $ 2 $ 的最长子串。

3. 题解

   二分答案，还是第一题那样分组，然后看看每一组中最大的 $ sa $ 和最小的 $ sa $ 之差是否大于等于mid。

4. 核心代码

   bool check(int x)
   {
       int minsa=0,maxsa=0;
       for(int i=1;i<=n;i++)
           if(height[i]<x)
           {
               minsa=sa[i];
               maxsa=sa[i];
           }
           else
           {
               minsa=min(minsa,sa[i]);
               maxsa=max(maxsa,sa[i]);
               if(maxsa-minsa>=x) return true;
           }
       return false;
   }

重复旋律三

1. 链接

   后缀数组三·重复旋律3

2. 题意

   求两个串的最长公共子串。

3. 题解

   在一个串后加一个不存在的字符后将另一个串接上去，求后缀数组后直接按 $ Rank $ 顺序跑，看相邻两个是否在两个串中。如果是，用这两个串的 $ LCP $ 更新答案。

4. 核心代码

for(int i=2;i<=n;i++)
   if(((1<=sa[i]&&sa[i]<=len1)!=(1<=sa[i-1]&&sa[i-1]<=len1))&&i!=len1+1&&i-1!=len1+1)
       	ans=max(ans,height[i]);

重复旋律四

1. 链接

   后缀数组四·重复旋律4

2. 题意

   给定一个串，求这个串的一个子串，使得这个子串是由数个相同的小子串构成的，且使重复次数最多。

3. 题解

   枚举小子串的长度 $ len $ ，然后将原串每隔 $ len $ 个点设一个特殊点。然后枚举每个特殊点，求出它与下一个特殊点的 $ LCP $ 。这两个特殊点的答案就是 $ \left \lfloor \frac{LCP}{len}+1 \right \rfloor $ 。然后考虑如果左端点不是在特殊点上的情况。我们将枚举的这个特殊点设为 $ p $ ，则我们只要看 $ p+l-LCP(p,p+l)\%len $ 这个点是否能使答案增加即可。

   由调和级数可知，总复杂度 $ O(nlogn) $ 。

4. 核心代码

   for(int len=1;len<=n;len++)
   {
       for(int i=1;i+len<=n;i+=len)
       {
           int R=query(i,i+len);
           ans=max(ans,R/len+1);
           if(i>=len-R%len)
           ans=max(ans,query(i-len+R%len,i+R%len)/len+1);
        }
   }