Cod sursa(job #3189629)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 6 ianuarie 2024 12:38:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, i, j, a[4000012], r;
vector<int> poz;
string p, t;

int main() {
    fin >> p >> t;
    t = p + "@" + t;
    n = t.size();
    for(i = 1; i < n; i++) {
        while(j > 0 && t[j] != t[i]) j = a[j - 1];
        if(t[j] == t[i]) j++;
        a[i] = j;

        if(a[i] == p.size()) {
            r++;
            poz.push_back(i - p.size() + 1);
        }
    }

    int f = min((int)poz.size(), 1000);
    fout << r << "\n";
    for(i = 0; i < f; i++) fout << poz[i] - p.size() - 1 << " ";

    return 0;
}