[BJWC2010] 外星联络

Description

求一个 \(01\) 串中所有重复出现次数大于 \(1\) 的子串所出现的次数，按照字典序排序输出。

Solution

预处理出后缀数组和高度数组。

对于每一个后缀 \(i\) ，如果 \(h[i+1]>h[i]\) ，我们就去找到在这之后对任意 \(j \in (h[i], h[i+1]]\) ，第一次出现 \(h[k]<j\) 的 \(k\) ，那么 \(k-i\) 就是这个子串出现的次数。

很不优美的解法，但是好像又没有别的办法。还不如直接建字典树。

#include <bits/stdc++.h>

using namespace std;

int n,m=256,sa[1000005],y[1000005],u[1000005],v[1000005],o[1000005],r[1000005],h[1000005],T;

char str[1000005];

long long ans;

int main()

{

    ios::sync_with_stdio(false);

    cin>>n;

    cin>>str+1;

    for(int i=1; i<=n; i++) u[str[i]]++;

    for(int i=1; i<=m; i++) u[i]+=u[i-1];

    for(int i=n; i>=1; i--) sa[u[str[i]]--]=i;

    r[sa[1]]=1;

    for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);

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

    {

        memset(u,0,sizeof u);

        memset(v,0,sizeof v);

        memcpy(o,r,sizeof r);

        for(int i=1; i<=n; i++) u[r[i]]++, v[r[i+l]]++;

        for(int i=1; i<=n; i++) u[i]+=u[i-1], v[i]+=v[i-1];

        for(int i=n; i>=1; i--) y[v[r[i+l]]--]=i;

        for(int i=n; i>=1; i--) sa[u[r[y[i]]]--]=y[i];

        r[sa[1]]=1;

        for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+((o[sa[i]]!=o[sa[i-1]])||(o[sa[i]+l]!=o[sa[i-1]+l]));

    }

    {

        int i,j,k=0;

        for(int i=1; i<=n; h[r[i++]]=k)

            for(k?k--:0,j=sa[r[i]-1]; str[i+k]==str[j+k]; k++);

    }

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

    {

        int l=h[i],r=h[i+1];

        if(l<r)

        {

            //cout<<"l="<<l<<" r="<<r<<endl;

            vector <int> tmp;

            ++l;

            for(int j=i+1; j<=n+1 && l<=r; j++)

            {

                while(r>h[j]&&l<=r)

                {

                    tmp.push_back(j-i);

                    --r;

                }

            }

            for(int j=tmp.size()-1; j>=0; --j)

                cout<<tmp[j]<<endl;

        }

    }

}

巴特西

[BJWC2010] 外星联络 - 后缀数组

[BJWC2010] 外星联络

Description

Solution

最新文章

热门文章