Cod sursa(job #2977714)

Utilizator alex_dacDumitrascu Constantin Alexandru alex_dac Data 12 februarie 2023 12:23:36
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;


#define ll long long
#define MAX 2000005


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


char pat[MAX],txt[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;
    }

    vector<int> pi(0,pat_l+1);
    int j=0;

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

    vector<int> poz;
    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[poz_k++]=i-pat_l+1;
            j=pi[j-1];

            if(poz_k>1000)
                break;
        }
    }
    out<<poz_k;
    for(int i=0;i<poz_k;i++){
        out<<poz[i]<<" ";
    }
    out<<endl;

    return 0;
}