Cod sursa(job #2653368)

Utilizator bogdi1bogdan bancuta bogdi1 Data 27 septembrie 2020 20:06:06
Problema Potrivirea sirurilor Scor 26
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
char s[4000005];
char s1[2000005];
int p[25][4000005];
int n,kk;
struct Pereche
{
    int cur,nxt;
};
struct Aux
{
    Pereche pereche;
    int pozitie;
} v[4000005];
struct Sortare
{
    int poz,ind;
} srt[4000005];
vector<int> sol;
bool cmp(const Aux &a, const Aux &b)
{
    if(a.pereche.cur==b.pereche.cur){
        if(a.pereche.nxt==b.pereche.nxt)
            return a.pozitie<b.pozitie;
        return a.pereche.nxt<b.pereche.nxt;
    }
    return a.pereche.cur<b.pereche.cur;
}
bool cmp2(const Sortare &a, const Sortare &b)
{
    return a.poz<b.poz;
}
int lcp(int i,int j)
{
    int l,i1,j1;
    if(i==j)
        return n-i;
    l=0;
    for(int put=kk; put>=0 && i<n && j<n; put--)
        if(p[put][i]==p[put][j]){
            i+=(1<<put);
            j+=(1<<put);
            l+=(1<<put);
        }
    return l;
}
int main()
{   freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int m,i,pw,j;
    scanf("%s", s1);
    scanf("%s", s);
    n=strlen(s);
    m=strlen(s1);
    s[n]='#';
    strcpy(s+n+1, s1);
    n=n+m+1;
    for(i=0; i<n; i++){
        if(s[i]>='a' && s[i]<='z')
            p[0][i]=s[i]-'a';
        else{
            if(s[i]>='A' && s[i]<='Z')
                p[0][i]=s[i]-'A'+26;
            else
                p[0][i]=52;
        }
    }
    for(kk=1,pw=1; pw/2<n; pw*=2,kk++){
        for(i=0; i<n; i++){
            v[i].pereche={p[kk-1][i], i+pw<n?p[kk-1][i+pw]:-1};
            v[i].pozitie=i;
        }
        sort(v, v+n, cmp);
        for(i=0; i<n; i++){
            if(i>0 && v[i].pereche.cur==v[i-1].pereche.cur && v[i].pereche.nxt==v[i-1].pereche.nxt)
                p[kk][v[i].pozitie]=p[kk][v[i-1].pozitie];
            else
                p[kk][v[i].pozitie]=i;
        }
    }
    kk--;
    for(i=0; i<n; i++){
        srt[i].poz=p[kk][i];
        srt[i].ind=i;
    }
    sort(srt, srt+n, cmp2);
    for(i=0; i<n; i++)
        if(srt[i].ind==n-m)
            break;
    for(j=i+1; j<n && sol.size()<1000; j++)
        if(lcp(srt[i].ind, srt[j].ind)==m)
            sol.push_back(srt[j].ind);
    printf("%d\n", sol.size());
    for(i=0; i<sol.size(); i++)
        printf("%d ", sol[i]);
    return 0;
}