Cod sursa(job #2977767)

Utilizator alex_dacDumitrascu Constantin Alexandru alex_dac Data 12 februarie 2023 13:32:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include<bits/stdc++.h>

using namespace std;

#define MAX 2000005

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


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

vector<int> poz;

void build_pi(){
    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;
    }
}

void show(){

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

}

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

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

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

    build_pi();

    int j=0;
    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){
            poz.push_back(i-pat_l+1);
            j=pi[j-1];

        }

    }

    show();
    return 0;
}