Cod sursa(job #2277237)

Utilizator remus88Neatu Remus Mihai remus88 Data 5 noiembrie 2018 21:35:03
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
#define NMAX 2000009
using namespace std;

#define USE_FILES 1

#ifdef USE_FILES
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
#endif // USE_FILES

string a, b;
char v[NMAX], T[NMAX];
int l1, l2, p[NMAX], sol;
set <int> s;

int main() {
    cin >> a >> b;
    l1 = a.size();
    l2 = b.size();
    for (int i = 0; i < l1; ++i) {
        v[i + 1] = a[i];
    }
    for (int i = 0; i < l2; ++i) {
        T[i + 1] = b[i];
    }

    int q = 0;
    for (int i = 1; i <= l2; ++i) {
        while (q && T[i] != v[q + 1]) {
            q = p[q];
        }
        if (T[i] == v[q + 1]) {
            ++q;
        }
        p[i] = q;
        if (q == l1) {
            q = p[l1];
        }
    }
    for (int i = 1; i <= l2; ++i) {
        if (p[i] == l1) {
            ++sol;
            s.insert(i - p[i]);
        }
    }
    cout << sol <<'\n';
    for (auto x : s) cout << x << ' ';
    return 0;
}