Cod sursa(job #2056605)

Utilizator AngelEclipseGarleanu Alexandru Stefan AngelEclipse Data 4 noiembrie 2017 12:29:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define Nmax 2000005
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[Nmax], H[Nmax];
int rsp[Nmax];
int S[Nmax], f, n, h, cnt;
int main()
{
    fin >> N + 1;
    n = strlen(N + 1);
    S[0] = -1;
    S[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        int k = i - 1;
        char c = N[i];
        while (S[k] != -1 && N[S[k] + 1] != c)
            k = S[k];
        S[i] = S[k] + 1;
    }
    fin >> H + 1;
    h = strlen(H + 1);
    f = 0;
    for (int i = 1; i <= h; i++)
    {
        while (f && N[f + 1] != H[i])
            f = S[f];
        if (N[f + 1] == H[i])
            f++;
        if (f == n)
        {
            f = S[f];
            cnt++;
            if (cnt <= 1000)
                rsp[cnt] = i - n;
        }
    }
    fout << cnt << '\n';
    for (int i = 1; i <= min(cnt, 1000); i++)
        fout << rsp[i] << " ";
    return 0;
}