Cod sursa(job #2352050)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 22 februarie 2019 22:03:36
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstring>
#include <fstream>

#define MAX 1000
#define SMAX 2000010

std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

int m; char a[SMAX];
int n; char b[SMAX];

int k;
int pre1[SMAX];
int pre2[SMAX];

int nrSol;
int sol[SMAX];

int main() {
    fin >> a; m = strlen(a);
    fin >> b; n = strlen(b);

    for (int i = 1; i < m; i++)
        if (a[k] == a[i])
            pre1[i] = ++k;
        else {
            while (a[k] != a[i] && k)
                k = pre1[k - 1];
            if (a[k] == a[i])
                k++;
            pre1[i] = k;
        }

    k = 0;
    for (int i = 0; i < n; i++)
        if (a[k] == b[i]) {
            pre2[i] = ++k;
            if (k == m)
                sol[nrSol++] = i - m + 1;
        }
        else {
            while (a[k] != b[i] && k)
                k = pre1[k - 1];
            if (a[k] == b[i])
                k++;
            pre2[i] = k;
        }

    fout << nrSol << '\n';
    for (int i = 0; i < nrSol && i < MAX; i++)
        fout << sol[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}