Cod sursa(job #2311053)

Utilizator Alexandru_StoianStoian Sorin Alexandru Alexandru_Stoian Data 2 ianuarie 2019 16:14:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[2000001],B[2000001];
int x,y;

int pr[1001],pos[1001];

void make_prefix(){
    int q=0,i=0;
    for(i=2, pr[1]=0; i<=x; ++i){
        while(q && A[i]!=A[q+1])
            q=pr[q];
        if(A[i]==A[q+1])
            ++q;
        pr[i]=q;
    }
}

int main(){
    f.getline(A,2000001);
    f.getline(B,2000001);

    x=strlen(A);
    y=strlen(B);

    for(int i=x; i>=1; --i)
        A[i]=A[i-1];
    A[0]='-';

    for(int i=y; i>=1; --i)
        B[i]=B[i-1];
    B[0]='-';

    make_prefix();

    int q=0,nr=0;

    for(int i=1; i<=y; ++i){
        while(q && A[q+1]!=B[i])
            q=pr[q];
        if(A[q+1]==B[i])
            ++q;
        if(q==x){
            q=pr[x];
            ++nr;
            if(nr<=1001)
                pos[nr]=i-x;
        }
    }

    nr=min(nr,1001);
    g<<nr<<'\n';
    for(int i=1; i<=nr; ++i)
        g<<pos[i]<<' ';
    g<<'\n';
    return 0;
}