[Solution][Suffixarray][Mid Search]USACO Musical Themes

【题目】

戳这里

【思路】

把原序列差分后用后缀数组求出不重叠的出现多次的最长公共子串,二分答案。

只需判断若干个height[]值大于mid的连续块内,是否有一个连续块的,如存在则说明当前答案合法。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int A[5030] , rank[5030] , height[5030] , sa[5030] , c[5030] ,Tmp0[5030] , Tmp1[5030];
void getrank(int n , int m)
{
    int *x = Tmp0 , *y = Tmp1 , i;
    for(i = 0 ; i < m ; ++i) c[i] = 0;
    for(i = 0 ; i < n ; ++i) ++c[x[i] = A[i]];
    for(i = 1 ; i < m ; ++i) c[i] += c[i - 1];
    for(i = n - 1 ; i >= 0 ; --i) sa[--c[x[i]]] = i;
    for(int k = 1 ; k <= n ; k <<= 1)
    {
        int p = 0;
        for(i = n - k ; i < n ; ++i) y[p++] = i;
        for(i = 0 ; i < n ; ++i)
            if (sa[i] >= k)
                y[p++] = sa[i] - k;
        for(i = 0 ; i < m ; ++i) c[i] = 0;
        for(i = 0 ; i < n ; ++i) ++c[x[y[i]]];
        for(i = 1 ; i < m ; ++i) c[i] += c[i - 1];
        for(i = n - 1 ; i >= 0 ; --i) sa[--c[x[y[i]]]] = y[i];
        swap(x , y);
        p = 1;
        x[sa[0]] = 0;
        for(i = 1 ; i < n ; ++i)
            x[sa[i]] = y[sa[i - 1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if (p >= n)
            break;
        m = p;
    }
}
void getheight(int n)
{
    register int i , j , k = 0;
    for(i = 0 ; i < n ; ++i) rank[sa[i]] = i;
    for(i = 0 ; i < n ; ++i)
    {
        if (k) --k;
        j = sa[rank[i] - 1];
        while(A[i + k] == A[j + k]) k++;
        height[rank[i]] = k;
    }
}
int main()
{
    int n;
    scanf("%d" , &n);
    register int i;
    for(i = 1 ; i <= n ; ++i)
        scanf("%d" , &A[i]);
    A[0] = 199;
    for(i = 1 ; i <= n ; ++i)
        A[i] = A[i] - A[i + 1] + 100;
    //A[n + 1] = 200;
    getrank(n + 1 , 200);
    getheight(n + 1);
    int L = 0 , R = n + 1;
    while(L + 1 < R)
    {
        int mid = (L + R) >> 1;
        int Min = height[0] , Max = height[0];
        bool flag = 0;
        for(i = 1 ; i < n + 1 ; ++i)
        {
            if (height[i] < mid)
            {
                if (Max - Min > mid)
                {
                    flag = 1;
                    break;
                }
                Min = Max = sa[i];
            }
            else
            {
                Min = sa[i] < Min ? sa[i] : Min;
                Max = sa[i] > Max ? sa[i] : Max;
            }
        }
        flag = Max - Min > mid;
        if (flag)
            L = mid;
        else
            R = mid;
    }
    printf("%d" , (L + 1) < 5 ? 0 : L + 1);
    return 0;
}
 
/***************************************************************
    Problem: 1829
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1100 kb
****************************************************************/

comments powered by Disqus