Cod sursa(job #2339668)

Utilizator TaveehOctavian Custura Taveeh Data 9 februarie 2019 11:02:37
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
//
//  main.cpp
//  strmatch
//
//  Created by Octavian Custura on 09/02/2019.
//  Copyright © 2019 Octavian Custura. All rights reserved.
//

#include <fstream>
#include <cstring>

int main() {
    std::ifstream fin ("strmatch.in");
    std::ofstream fout ("strmatch.out");
    char s[2000001], t[2000001];
    int sol[1001], p[200001];
    fin >> (s + 1);
    fin >> (t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    int L = 0;
    p[1] = 0;
    for (int i = 2; i <= n; ++i) {
        while (L != 0 && s[i] != s[L + 1]) {
            L = p[L];
        }
        if (s[i] == s[L + 1]) {
            L++;
        }
        p[i] = L;
    }
    L = 0;
    int ap = 0;
    for (int i = 1; i <= m; ++i) {
        while (L != 0 && t[i] != s[L + 1]) {
            L = p[L];
        }
        if (t[i] == s[L + 1]) {
            L++;
        }
        if (L == n) {
            ap++;
            if (ap <= 1000) {
                sol[ap] = i - n;
            }
            L = p[L];
        }
    }
    fout << ap << '\n';
    if (ap > 1000) {
        ap = 1000;
    }
    for (int i = 1; i <= ap; ++i) {
        fout << sol[i] << ' ';
    }
    return 0;
}