Cod sursa(job #3001973)

Utilizator vlad_maneaManea Vlad Cristian vlad_manea Data 14 martie 2023 09:54:10
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

vector<int> pos;

char a[2000005], b[2000005];
int n, m, pi[2000005];

void citire() {
    fin>>a>>b;
    n=strlen(a+1);
    m=strlen(b+1);
}

void prefix() {
    int k=0;
    for (int i=2; i<=n; i++) {
        while (k && a[k+1]!=a[i])
            k=pi[k];
        if (a[k+1]==a[i])
            k++;
        pi[i]=k;
    }
}

void kmp() {
    int q=0;
    for (int i=1; i<=m; i++) {
        while (q && a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            q++;
        if (q==n)
            pos.push_back(i-n);
    }
}

void afisare() {
    fout<<pos.size()<<"\n";
    int nr=0;
    for (auto i: pos) {
        nr++;
        fout<<i<<" ";
        if (nr>1000)
            exit(0);
    }

}

int main() {
    citire();
    prefix();
    kmp();
    afisare();
    return 0;
}