Cod sursa(job #2376529)

Utilizator AndoneAlexandruAndone Alexandru AndoneAlexandru Data 8 martie 2019 16:11:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;

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

int z[4000005];
string text, pattern, concat;

void generateZarr();

void solve() {
    concat = pattern + "$" + text;
    int l = concat.length();
    int p = pattern.length();

    generateZarr();

    int nr = 0;
    for (int i = 0; i < l; ++i)
        if (z[i] == p)
            nr++;
    out << nr << '\n';
    nr = 0;
    for (int i = 0; i < l && nr < 1000; ++i)
        if (z[i] == p) {
            out << i - p - 1 << ' ';
            ++nr;
        }
}

void generateZarr() {
    int n = concat.length();
    int L = 0, R = 0, k;

    for (int i = 1; i < n; ++i) {
        if (i > R) {
            R = L = i;
            while (R < n && concat[R-L] == concat[R])
                R++;
            z[i] = R - L;
            R--;
        }
        else {
            k = i - L;
            if (z[k] < R-i+1)
                z[i] = z[k];
            else {
                L = i;
                while (R < n && concat[R-L] == concat[R])
                    R++;
                z[i] = R - L;
                R--;
            }
        }
    }
}

int main() {
    getline(in, pattern);
    getline(in, text);
    solve();
}