Cod sursa(job #2553201)

Utilizator mihhTURCU MIHNEA ALEXANDRU mihh Data 21 februarie 2020 18:50:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 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];
string T,P;
int k;
int a[N],lps[N];

int main(){
    fin>>P>>T;

    KMP();

    fout<<k<<"\n";
    if(k>1000) k=1000;
    for(int i=1;i<=k;++i)
        fout<<a[i]<<' ';
}

void Pref(){

    int j=0;

    for(int i=1;i<P.size();++i){
        int i2=i;
        for(;i<N and P[i]==P[i-i2]; ++i)
            lps[i]=i-i2+1;
        if(i2!=i) --i;
    }
}


void KMP()
{
    Pref();
    int q=0;
    for(int i=0;i<T.size();++i){

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

        if(P[q]==T[i]) ++q;
        if(q==P.size()) a[++k]=i-P.size()+1;
    }



}