Cod sursa(job #3235831)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 22 iunie 2024 09:48:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

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

int main() {
    fin >> a >> b;
    b = a + "@" + b;

    n = b.size();
    for(i = 1; i < n; i++) {
        while(j > 0 && b[j] != b[i]) j = l[j - 1];
        if(b[j] == b[i]) j++;
        l[i] = j;

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

    int lim = min((int)poz.size(), 1000);

    fout << r << "\n";
    for(i = 0; i < lim; i++) fout << poz[i] - a.size() - 1 << " ";

    return 0;
}