Cod sursa(job #2977727)

Utilizator alex_dacDumitrascu Constantin Alexandru alex_dac Data 12 februarie 2023 12:59:26
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <cstring>


using namespace std;

#define MAX 2000005

ifstream in("strmatch.in");
ofstream out("strmatch.out");


char pat[MAX],txt[MAX];
int poz[1024],pi[MAX];
int txt_l,pat_l;
int poz_k;


int main() {
    in.getline(pat,MAX);
    in.getline(txt,MAX);

    txt_l=strlen(txt);
    pat_l=strlen(pat);

    if(txt_l<pat_l){
        out<<0;
        return 0;
    }

    int j=0;
    for(int i=1;i<pat_l;i++){
        while(j and pat[i]!=pat[j])
            j=pi[j-1];
        if(pat[i]==pat[j])
        j++;
        pi[i]=j;
    }


    for(int i=0;i<txt_l;i++){
        while(j and pat[j]!=txt[i])
            j=pi[j-1];

        if(pat[j]==txt[i])
            j++;

        if(j==pat_l){
            if(poz_k<1001)
            poz[poz_k++]=i-j+1;

            j=pi[j-1];

        }

    }
    out<<poz_k<<"\n";
    for(int i=0;i<min(poz_k,1000);i++){
        out<<poz[i]<<" ";
    }
    out<<"\n";

    return 0;
}