Cod sursa(job #2339608)

Utilizator TaveehOctavian Custura Taveeh Data 9 februarie 2019 10:21:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <cstring>
int main(int argc, const char * argv[]) {
    std::ifstream fin ("strmatch.in");
    std::ofstream fout("strmatch.out");
    char t[2000001], s[20000001];
    int p[2000001], sol [1001];
    fin >> (s + 1);
    fin >> (t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    int ap = 0;
    //calculam p[i] - lungimea maxima a unui sufix terminat la pozitia care totodata este prefix al lui s
    p[1] = 0;
    int L = 0;
    for (int i = 2; i <= n; ++i) {
        //calculam P[i]
        while (L != 0 && s[i] != s[L + 1]) {
            L = p[L];
        }
        if (s[i] == s[L + 1]) {
            L++;
        }
        p[i] = L;
    }
    L = 0;
    for (int i = 1; i <= m; ++i) {
        // voi testa potrivire a lui s in t care se termina la pozitia i
        // semnificatia lui L la pasul i - lungimea maxima a unui sufix din t terminat la pozitia i
        // care totodata este prefix de lungime L in s;
        while (L != 0 && t[i] != s[L + 1]) {
            L = p[L];
        }
        if (t[i] == s[L + 1]) {
            L++;
        }
        if (L == n) {
            // potrivire
            ap++;
            if(ap <= 1000) {
                sol[ap] = L - n;
            }
            L = p[L]; // urmatoarea potrivire se poate suprapune cu cea curenta si o cautam extinzand cel mai lung prefix al intregului sir s
            
        }
    }
    fout << ap << '\n';
    for (int i = 1; i <= ap; ++i) {
        fout << sol[i] << ' ';
    }
    return 0;
}