Общая подстрока

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>

#define pb push_back
#define mp make_pair
#define fr first
#define se second
#define sc scanf
#define pr printf

const double eps = 1e-12;
const int zero1 = 256;
const int MN = 50010;
const int N = 8000;
const int inf = 1000010;

using namespace std;
int n = 0, k, ls1, ls2;
int p[MN], c[20][MN], ps2[20][MN], lps2[20];
char s1[MN], s2[MN], s[MN];
void Init(){
    sc("%s", s1);
    sc("%s", s2);
    sc("%d", &k);
    ls1 = strlen(s1);
    ls2 = strlen(s2);
    for(int i=0; i<N; i++){
        s[n++] = '#';
    }
    for(int i=0; i<ls1; i++){
        s[n++] = s1[i];
    }
    for(int i=0; i<N; i++){
        s[n++] = '#';
    }
    for(int i=0; i<ls2; i++){
        s[n++] = s2[i];
    }
    //pr("%s\n", s);
    //pr("%d %d\n", ls1, ls2);
}
int LCP(int i, int j, int h){
    int cur = 0;
    for(; h>=0; h--){
        if(c[h][i] == c[h][j] && i+(1<<h)<=N+ls1 && j+(1<<h)<=N+ls1){
            cur += (1<<h);
            i += (1<<h);
            j += (1<<h);
        }
    }
    return cur;
}
int find(int i, int ln){
    int h = 0;
    while((1<<h)<=ln)h++;
    h--;
    pair<int, int>a, b;
    int L = 0, M, j, R, H;
    if((1<<h) == ln){
        H = h;
    }
    else {
        H = h+1;
    }
    R = lps2[H]-1;
    if(R == -1)return 0;
    while(L<R){
        M = (L+R)/2;
        j = ps2[H][M];
        a = mp(c[h][i], c[h][ i+ln-(1<<h) ]);
        b = mp(c[h][j], c[h][ j+ln-(1<<h) ]);
        if(a>b){
            L = M+1;
        }
        else {
            R = M;
        }
    }
    j = ps2[H][R];
    a = mp(c[h][i], c[h][ i+ln-(1<<h) ]);
    b = mp(c[h][j], c[h][ j+ln-(1<<h) ]);
    return (a == b);
}
int classes, cnt[MN], pn[MN];
void solve(){
    memset(cnt, 0, zero1*sizeof(int));
    for(int i=0; i<n; i++){
        cnt[ s[i] ]++;
    }
    for(int i=1; i<zero1; i++){
        cnt[i] += cnt[i-1];
    }
    for(int i=0; i<n; i++){
        p[ --cnt[ s[i] ] ] = i;
    }
    for(int i=0; i<n; i++){
        if(p[i]>=N+N+ls1){
            ps2[0][ lps2[0]++ ] = p[i];
        }
    }
    c[0][ p[0] ] = 0;
    classes = 1;
    for(int i=1; i<n; i++){
        if(s[ p[i] ] != s[ p[i-1] ]){
            classes++;
        }
        c[0][ p[i] ] = classes-1;
    }


    for(int h=0; (1<<h)<ls1; h++){
        for(int i=0; i<n; i++){
            pn[i] = p[i]-(1<<h);
            if(pn[i]<0){
                pn[i] += n;
            }
        }
        memset(cnt, 0, classes*sizeof(int));
        for(int i=0; i<n; i++){
            cnt[ c[h][ pn[i] ] ]++;
        }
        for(int i=1; i<classes; i++){
            cnt[i] += cnt[i-1];
        }
        for(int i=n-1; i>=0; i--){
            p[ --cnt[ c[h][ pn[i] ] ] ] = pn[i];
        }
        for(int i=0; i<n; i++){
            if(p[i]>=N+N+ls1){
                ps2[h+1][ lps2[h+1]++ ] = p[i];
            }
        }
        c[h+1][ p[0] ] = 0;
        classes = 1;
        for(int i=1; i<n; i++){
            int min1 = (p[i]+(1<<h))%n;
            int min2 = (p[i-1]+(1<<h))%n;
            if(c[h][ p[i] ] != c[h][ p[i-1] ] || c[h][ min1 ] != c[h][ min2 ]){
                classes++;
            }
            c[h+1][ p[i] ] = classes-1;
        }
    }
    int q = 0;
    for(int i=0; i<n; i++){
        if(p[i]>=N && p[i]<N+ls1){
            p[q++] = p[i];
        }
    }
    /*
    for(int i=0; i<q; i++){
        pr("%d ", p[i]);
    }
    pr("\n");
    */
    int h = 0, lcp[MN] = {0};
    while((1<<h)<=ls1)h++;
    h--;
    for(int i=1; i<q; i++){
        lcp[i] = LCP(p[i], p[i-1], h);
        //pr("%d %d %d\n", p[i], p[i-1], lcp[i]);
    }
    for(int i=0; i<q; i++){
        for(int j=lcp[i]+1; j+p[i]<=N+ls1; j++){
            k -= find(p[i], j);
            if(k == 0){
                for(k=0; k<j; k++){
                    pr("%c", s[ p[i]+k ]);
                }
                pr("\n");
                exit(0);
            }
        }
    }
}
main(){
    freopen("input.txt", "r", stdin);    freopen("output.txt", "w", stdout);
    //freopen("paint.in", "r", stdin);    freopen("paint.out", "w", stdout);
    Init();
    solve();
    return 0;
}