Cod sursa(job #2553019)

Utilizator mihhTURCU MIHNEA ALEXANDRU mihh Data 21 februarie 2020 15:05:50
Problema Potrivirea sirurilor Scor 38
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 S[i-i2]==S[i];)
            lps[i++]=i-i2;
//        if(i2!=i) --i;
    }
    /// pre kmp

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

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

        int len=0;
        for(j=i; j<S.size() and S[j]==P[len];++len)
            cout<<len<<" ", ++j;
        cout<<"\n";

        if(len==P.size())
            poz.push_back(i);
        else i+=lps[len];
    }
}

int main(){

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