Submission #2499770

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define MAXN    (200010)
namespace mzry_sa
{
    int wx[MAXN],wy[MAXN],*x,*y,wss[MAXN],wv[MAXN];

    bool dacmp(int *r,int n,int a,int b,int l) {
        return a+l<n && b+l<n && r[a]==r[b]&&r[a+l]==r[b+l];
    }
    void da(int str[],int sa[],int rank[],int height[],int n,int m) {
        int *s = str;
        int *x=wx,*y=wy,*t,p;
        int i,j;
        for(i=0; i<m; i++)wss[i]=0;
        for(i=0; i<n; i++)wss[x[i]=s[i]]++;
        for(i=1; i<m; i++)wss[i]+=wss[i-1];
        for(i=n-1; i>=0; i--)sa[--wss[x[i]]]=i;
        for(j=1,p=1; p<n && j<n; j*=2,m=p) {
            for(i=n-j,p=0; i<n; i++)y[p++]=i;
            for(i=0; i<n; i++)if(sa[i]-j>=0)y[p++]=sa[i]-j;
            for(i=0; i<n; i++)wv[i]=x[y[i]];
            for(i=0; i<m; i++)wss[i]=0;
            for(i=0; i<n; i++)wss[wv[i]]++;
            for(i=1; i<m; i++)wss[i]+=wss[i-1];
            for(i=n-1; i>=0; i--)sa[--wss[wv[i]]]=y[i];
            for(t=x,x=y,y=t,p=1,i=1,x[sa[0]]=0; i<n; i++)
            x[sa[i]]=dacmp(y,n,sa[i-1],sa[i],j)?p-1:p++;
        }
        for(int i=0; i<n; i++) rank[sa[i]]=i;
        for(int i=0,j=0,k=0; i<n; height[rank[i++]]=k)
            if(rank[i]>0)
            for(k?k--:0,j=sa[rank[i]-1];
                i+k < n && j+k < n && str[i+k]==str[j+k];
                k++);
    }
}

#define MAXS    5196
char s[MAXS];
int sl;
int k;
int si[MAXS];
int sa[MAXS];
int myrank[MAXS];
int height[MAXS];

typedef unsigned int ui;
const ui P = 772002u;
ui nP[MAXS];
ui H[MAXS];

void myinit(void)
{
    int i;
    nP[0] = 1;
    for(i = 1;i <= sl;++i)
        nP[i] = nP[i-1] * P;
    H[0] = 0u;
    for(i = 1;i <= sl;++i)
        H[i] = H[i-1] * P + (ui)(s[i-1]);
}

int main(void)
{
    int i, j;
    scanf("%s", s); sl = strlen(s);
    myinit();
    scanf("%d", &k);
    for(i = 0;i < sl;++i)
        si[i] = s[i] - 'a' + 1;
    si[sl] = 0;
    mzry_sa::da(si, sa, myrank, height, sl+1, 27);
    set<ui> app;
    for(i = 1;i <= sl;++i)
    {
        int l = sa[i], r = sa[i];
        for(r = sa[i];r < sl;r++)
        {
            ui h = H[r+1] - H[l] * nP[r-l+1];
            if(app.end() == app.find(h))
            {
                app.insert(h);
                k--;
                if(0 == k)
                {
                    for(j = l;j <= r;j++)
                        putchar(s[j]);
                    puts("");
                    return 0;
                }
            }
        }
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s); sl = strlen(s);
                   ^
./Main.cpp:71:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
                    ^

Judge Result