Cod sursa(job #2417335)

Utilizator claudiapopescuPopescu Claudia claudiapopescu Data 29 aprilie 2019 15:54:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

const int Dim = 2e6 + 5;

char a[Dim], b[Dim];

int pi[Dim], pos[Dim];
int n, m, ans, k;

int main() {
    f >> (a + 1) >> (b + 1);
    n = strlen (a + 1);
    m = strlen (b + 1);

    for (int i = 2; i <= n; ++ i) {
        while (k > 0 && a[k + 1] != a[i]) {
            k = pi[k];
        }

        if (a[k + 1] == a[i]) {
            ++ k;
        }

        pi[i] = k;
    }

    k = 0;
    for (int i = 1; i <= m; ++ i) {
        while (k > 0 && a[k + 1] != b[i]) {
            k = pi[k];
        }

        if (a[k + 1] == b[i]) {
            ++ k;
        }

        pos[i] = k;
    }

    for (int i = 1; i <= m; ++ i) {
        if (pos[i] == n) ++ ans;
    }

    g << ans << '\n';
    ans = 0;
    for (int i = 1; i <= m; ++ i) {
        if (pos[i] == n) {
            g << i - n << " ";
            ++ ans;
        }

        if (ans == 1000)
            return 0;
    }

    return 0;
}