Cod sursa(job #2553105)

Utilizator mihhTURCU MIHNEA ALEXANDRU mihh Data 21 februarie 2020 16:58:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 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];)
            lps[i++]=i-i2;
    }
    /// pre kmp
    for(int i=0;i<P.size();++i)
        cout<<lps[i]<<" ";
    //
    for(int i=0,j=0; i<S.size();)
    {
        if(S[i]==P[j]) ++i, ++j;

        if(j==P.size())
            poz.push_back(i-j),
            j=lps[j-1];

        else if(i<S.size() and P[j]!=S[i])
        {
            if(j)
                j=lps[j-1];
            else ++i;
        }
    }
}

int main(){

    fin>>P>>S;
    KMP();
    fout<<poz.size()<<"\n";
    for(int i=0; i<poz.size(); ++i)
        fout<<poz[i]<<" ";
}