Cod sursa(job #2616725)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 19 mai 2020 20:54:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 2000005;

struct idk{
    int fh,sh,poz;
};
idk v[NMAX];
char a[NMAX],b[NMAX];
int dp[25][NMAX],st,dr;
int rasp[NMAX];
int n,step,put,m;

bool cmp(idk a,idk b){
    if(a.fh==b.fh) return a.sh<b.sh;
                     return a.fh<b.fh;
}

int lcp(int x,int y){
    if(x==y) return n-x+1;
    int rasp=0;
    for(int i=step-1;i>=0;i--){
        if(x>n or y>n) break;
        if(dp[i][x]==dp[i][y]){
            x+=(1<<i);
            y+=(1<<i);
            rasp+=(1<<i);
        }
    }
    return rasp;
}

int main()
{
    fin >> (b+1);
    fin >> (a+1);
    n=strlen(a+1);
    int aux=n;
    m=strlen(b+1);
    a[n+1]='#';
    for(int i=n+2;i<=n+m+1;i++){
        a[i]=b[i-n-1];
    }
    n=n+m+1;
    for(int i=1;i<=n;i++){
        dp[0][i]=a[i]-'a';
    }
    step=0,put=1;
    while(put/2<n){
        step++;
        for(int i=1;i<=n;i++){
            v[i].fh=dp[step-1][i];
            if(i+put>n) v[i].sh=-1;
            else v[i].sh=dp[step-1][i+put];
            v[i].poz=i;
        }
        sort(v+1,v+n+1,cmp);
        dp[step][v[1].poz]=1;
        int ind=1;
        for(int i=2;i<=n;i++){
            if(v[i].fh==v[i-1].fh and v[i].sh==v[i-1].sh)
                dp[step][v[i].poz]=dp[step][v[i-1].poz];
            else {
                dp[step][v[i].poz]=++ind;
            }
        }
        put*=2;
    }
    int rr=0;
    int dim_rasp=0;
    for(int i=1;i<=aux;i++){
        int nr=lcp(i,aux+2);
        if(nr==m){
            rr++;
            rasp[++dim_rasp]=i;
        }
    }
    fout << rr << '\n';
    for(int i=1;i<=dim_rasp;i++) fout << rasp[i]-1 << ' ';
    return 0;
}