Cod sursa(job #2374274)

Utilizator aturcsaTurcsa Alexandru aturcsa Data 7 martie 2019 17:46:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

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

int n, h, i, F[4000005], k, S[1001];
char N[4000005], H[4000005];
int main()
{
    f >> N+1;
    f >> H + 1;
    n = strlen(N + 1);
    h = strlen(H + 1);
    i = 0;
    F[1] = 0;
    strcat(N+1, "$");
    strcat(N+1, H + 1);
    for (int j = 2; j <= n + h + 1 && k < 1000; j++)
    {
        while (i > 0 && N[i + 1] != N[j])
            i = F[i];
        if (N[i + 1] == N[j])
            i = i + 1;
        F[j] = i;
        if (F[j] == n)
        {
            k++;
            S[k] = j - 2 * n - 1;
        }
    }
    g << k << '\n';
    for (int j = 1; j <= k; j++)
        g << S[j] << ' ';
    f.close();
    g.close();
    return 0;
}