Cod sursa(job #2977721)

Utilizator alex_dacDumitrascu Constantin Alexandru alex_dac Data 12 februarie 2023 12:44:42
Problema Potrivirea sirurilor Scor 14
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>


using namespace std;

#define MAX 2000005

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


char pat[MAX],txt[MAX];
int poz[1020];
int txt_l,pat_l;
int poz_k;
vector<int> pi;


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;
    pi[0]=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;
    }
    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){
            j=pi[j-1];

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

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

    return 0;
}