Cod sursa(job #2266751)

Utilizator remus88Neatu Remus Mihai remus88 Data 22 octombrie 2018 21:13:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define Nmax 40000009
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

int z[Nmax];
string a,b;
char P[Nmax];
set <int> s;

void strbuild(string a, string b) {
    int l1 = a.size();
    int l2 = b.size();


    for (int i = 0; i < l1; ++i) {
        P[i + 1] = a[i];
    }
    P[l1+1] = '#';
    for (int i = 0; i < l2; ++i) {
        P[l1 + i + 2] = b[i];
    }
}

void Z(char P[Nmax], int n) {
    z[1] = 0;
    int l = 0, r = 0;
    for (int i = 2; i <= n; ++i) {
        if (i <= r) {
            z[i] = min(z[i - l], r - i + 1);
        }

        while (i + z[i] - 1 <= n  &&  P[i + z[i]] == P[z[i] + 1]) {
            ++z[i];
        }

        if (i + z[i] - 1 >= r) {
            r = i + z[i] -1;
            l = i;
        }
    }
}

int main() {

    cin >> a >> b;

    int l1 = a.size();
    int l2 = b.size();

    strbuild(a, b);

    int n = l1 + l2 +1;

 //   for (int i = 1; i <= n; ++i) cout << P[i];

    Z(P, n);

    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (z[i] == l1) {
            ++cnt;
            s.insert(i);
        }
    }

    cout << cnt << '\n';
    for (auto x: s) cout << x - l1 - 2 << ' ';

    return 0;
}