Cod sursa(job #2154919)

Utilizator osiaccrCristian Osiac osiaccr Data 7 martie 2018 13:43:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <cstring>
#define DEF 2000010
#define DEFS 1010

using namespace std;

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

char s[DEF], t[DEF];

int n, m, L, P[DEF], sol, Sol[DEFS];

/// Caut o aparitie a lui t in s
/// m = lungimea lui t
/// n = lungimea lui s

int main () {
    fin >> t + 1 >> s + 1;
    m = strlen (t + 1);
    n = strlen (s + 1);

    for (int i = 2; i <= m; ++ i) {
        while (L != 0 and t[i] != t[L + 1]) {
            L = P[L];
        }

        if (t[i] == t[L + 1]) {
            ++ L;
        }

        P[i] = L;
    }

    L = 0;
    for (int i = 1; i <= n; ++ i) {
        while (L != 0 and s[i] != t[L + 1]) {
            L = P[L];
        }

        if (s[i] == t[L + 1]) {
            ++ L;
        }

        if (L == m) {
            ++ sol;
            if (sol <= 1000)
                Sol[sol] = i - m;
            L = P[L];
        }
    }

    fout << sol << "\n";
    sol = min (sol, 1000);
    for (int i = 1; i <= sol; ++ i) {
        fout << Sol[i] << " ";
    }

    return 0;
}