Cod sursa(job #2977745)

Utilizator alex_dacDumitrascu Constantin Alexandru alex_dac Data 12 februarie 2023 13:14:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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,j=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;
            poz_k++;
            j=pi[j-1];

        }

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

    return 0;
}