Cod sursa(job #2352094)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 22 februarie 2019 22:40:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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 pre1[SMAX];
int pre2[SMAX];

int nrSol;
int sol[SMAX];

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

    int k = 0;
    for (int i = 1; i < m; i++) {
        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++) {
        while (a[k] != b[i] && k)
            k = pre1[k - 1];
        if (a[k] == b[i])
            k++;
        pre2[i] = k;

        if (k == m)
            sol[nrSol++] = i - m + 1;
    }

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

    fout.close();
    return 0;
}