Cod sursa(job #2896814)

Utilizator BuzatuCalinBuzatu Calin BuzatuCalin Data 30 aprilie 2022 21:12:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
using namespace std;
#define DIM 2000001
int pi[DIM],n,m,rasp[DIM],r;
string P,T;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calcul_pi_prefix(){
    int k=0;
    for(int q=2;q<=m;q++){
        while(k>0 && P[k+1]!=P[q])
        {
            k=pi[q];
        }
        if(P[k+1]==P[q])
        {
            k++;
        }
        pi[q]=k;
    }
}
void potrivire_KMP(){
    calcul_pi_prefix();
    int q=0;
    for(int i=1;i<=n;i++)
    {
        while(q>0 && P[q+1]!=T[i]){
            q=pi[q];
        }
        if(P[q+1]==T[i])
        {
            q++;
        }
        if(q==m)
        {
            rasp[r]=i-m;
            r++;
            q=pi[q];
        }
    }
}
int main(){
    fin>>P>>T;
    P.resize(P.length()+1);
    T.resize(T.length()+1);
    m=P.length()-1;n=T.length()-1;
    for(int i=m;i>=1;i--)
    {
        P[i]=P[i-1];
    }
    for(int i=n;i>=1;i--)
    {
        T[i]=T[i-1];
    }
    potrivire_KMP();
    fout<<r<<'\n';
    for(int i=0;i<r;i++){
        fout<<rasp[i]<<' ';
    }
}