Cod sursa(job #3188575)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 3 ianuarie 2024 13:30:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, pi[4000002], i, j;
string p, s;
queue<int> q;

static inline void CalcPi() {
    pi[0] = 0;
    j = 0;
    for(i = 1; i < m; i++) {
        while(j != 0 && p[i] != p[j]) j = pi[j - 1];
        if(p[i] == p[j]) j++;
        pi[i] = j;
    }
}

static inline void Cauta() {
    j = 0;
    for(i = 0; i < n; i++) {
        while(j != 0 && p[j] != s[i]) j = pi[j - 1];
        if(p[j] == s[i]) j++;
        if(j == m && q.size() < 1000) q.push(i - m + 1);
    }
}

int main() {
    fin >> p >> s;
    n = s.size();
    m = p.size();

    CalcPi();
    Cauta();

    fout << q.size() << "\n";
    while(!q.empty()) {
        fout << q.front() << " ";
        q.pop();
    }

    return 0;
}