Cod sursa(job #2552987)

Utilizator mihhTURCU MIHNEA ALEXANDRU mihh Data 21 februarie 2020 13:57:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;

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


void Citire();
void Pref();
void KMP();

char T[N],P[N];
int n,m,k;
int a[N],urm[N];

int main()
{
    Citire();
    KMP();
    fout<<k<<'\n';
    if(k>1000) k=1000;
    for(int i=1;i<=k;++i)
        fout<<a[i]<<' ';

    return 0;
}


void Citire(){
    fin.getline(P,N);
    fin.getline(T,N);
    n=strlen(P);
    m=strlen(T);
}

void Pref(){
    int j=0;
//    for(int i=1;i<n;++i)

//    {

//        while(j>0 && P[i]!=P[j]) j=urm[j-1];

//        if(P[i] == P[j]) ++j;

//        urm[i]=j;

//    }

//
    for(int i=1;i<n;++i){
        int i2=i;
        for(;i<N and P[i]==P[i-i2]; ++i)
            urm[i]=i-i2+1;
        if(i2!=i) --i;

    }

//    for(int i=0;i<n;++i)

//        cout<<urm[i]<<" ";

}



void KMP()

{

    Pref();

    int q=0;

    for(int i=0;i<m;++i)

    {

        while(q>0 && P[q]!=T[i]) q=urm[q-1];

        if(P[q]==T[i]) ++q;

        if(q==n) a[++k]=i-n+1;

    }

}