Cod sursa(job #2553225)

Utilizator mihhTURCU MIHNEA ALEXANDRU mihh Data 21 februarie 2020 19:12:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;



ifstream fin("strmatch.in");

ofstream fout("strmatch.out");



const int NMAX=2000005;



string S,P;

int lps[NMAX];

vector <int> poz;



void KMP(){



    for(int i=1; i<P.size(); ++i){



        int i2=i;

        for(;i<P.size() and P[i]==P[i-i2]; ++i)

            lps[i]=i-i2+1;

        if(i!=i2) --i;

    }

    /// pre kmp



    int q=0;

    for(int i=0; i<S.size(); ++i)
    {

        for(;q>0 and S[i]!=P[q];)
            q=lps[q-1];

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

        if(q==P.size()) poz.push_back(i-q+1);

    }

}



int main(){

    fin>>P>>S;
    KMP();


    fout<<poz.size()<<"\n";
    poz.resize(min(int(poz.size()),1000));

    for(int i=0; i<poz.size()    ; ++i)
        fout<<poz[i]<<" ";

}