Cod sursa(job #1670099)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 31 martie 2016 14:06:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <string.h>
#include <fstream>

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

int n, m;
int prefix[2000005], pos[1005], nr;
char N[2000005], M[2000005];

int main()
{
    f.getline(M+1, 2000002);
    f.getline(N+1, 2000002);
    n = strlen(N+1);
    m = strlen(M+1);
    int q = 0;
    for(int i = 2; i <= m; i++)
    {
        while(q && M[q+1] != M[i]) q = prefix[q];
        if(M[q+1] == M[i]) q++;
        prefix[i] = q;
    }
    q = 0;
    for(int i = 1; i <= n; i++)
    {
        while(q && M[q+1] != N[i]) q = prefix[q];
        if(M[q+1] == N[i]) q++;
        if(q == m)
        {
            nr++;
            q = prefix[q];
            if(nr <= 1000) pos[nr] = i-m;
        }
    }
    g<<nr<<'\n';
    nr = min(nr, 1000);
    for(int i = 1; i <= nr; i++) g<<pos[i]<<' ';
    g<<'\n';
    return 0;
}