头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Bzoj 1031 字符加密

描述:

传送门


思路:

把字符串倍增一份,然后求后缀数组就好。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**************************************************************
    Problem: 1031
    User: Decaku
    Language: C++
    Result: Accepted
    Time:1336 ms
    Memory:29612 kb
****************************************************************/
 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,m;
int x[maxn],y[maxn],t[maxn],sa[maxn],rk[maxn],height[maxn];
char s[maxn];
int a[maxn];
bool cmp(int i,int j,int k)
{
    return y[i]==y[j]&&y[i+k]==y[j+k];
}
void get_sa()
{
    //int m=30;
    for(int i=1; i<=n; ++i)
        t[x[i]=a[i]]++;
    for(int i=1; i<=m; ++i)
        t[i]+=t[i-1];
    for(int i=n; i>=1; --i)
        sa[t[x[i]]--]=i;
    for(int k=1; k<=n; k<<=1)
    {
        int p=0;
        for(int i=0; i<=m; ++i)
            y[i]=0;
        for(int i=n-k+1; i<=n; ++i)
            y[++p]=i;
        for(int i=1; i<=n; ++i)
            if(sa[i]>k)
                y[++p]=sa[i]-k;
        for(int i=0; i<=m; ++i)
            t[i]=0;
        for(int i=1; i<=n; ++i)
            t[x[y[i]]]++;
        for(int i=1; i<=m; ++i)
            t[i]+=t[i-1];
        for(int i=n; i>=1; --i)
            sa[t[x[y[i]]]--]=y[i];
        swap(x,y);
        x[sa[1]]=p=1;
        for(int i=2; i<=n; ++i)
            x[sa[i]]=cmp(sa[i],sa[i-1],k)?p:++p;
        if(p>=n)
            break;
        m=p;
    }
}
 
void get_rk()
{
    for(int i=1; i<=n; ++i)
        rk[sa[i]]=i;
}
void get_height()
{
    for(int i=1,j=0; i<=n; ++i)
    {
        if(j)
            j--;
        while(a[i+j]==a[sa[rk[i]-1]+j])
            ++j;
        height[rk[i]]=j;
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=n+1;i<=2*n;i++)
        s[i]=s[i-n];
    for(int i=1;i<=2*n;i++)
        a[i]=s[i];
    n*=2;
    m=500;
    get_sa();
    for(int i=1;i<=n;i++)
    {
        if(sa[i]<=n/2)
        {
            printf("%c",s[sa[i]+n/2-1]);
        }
    }
    printf("\n");
 
}
avatar Decaku 很菜但也很想carry