Cod sursa(job #2154900)

Utilizator osiaccrCristian Osiac osiaccr Data 7 martie 2018 13:38:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <cstring>
#include <vector>
#define DEF 2000010

using namespace std;

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

char s[DEF], t[DEF];

int n, m, L, P[DEF];

vector < int > Sol;

/// 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.push_back (i - m);
            L = P[L];
        }
    }

    fout << Sol.size () << "\n";
    for (int i = 0; i < Sol.size (); ++ i) {
        fout << Sol[i] << " ";
    }

    return 0;
}