Cod sursa(job #856605)

Utilizator SteveStefan Eniceicu Steve Data 16 ianuarie 2013 19:38:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#define pb push_back

using namespace std;

int N, M, cnt;
char A[2000011];
char B[2000011];
int Pi[2000011];
int v[1011];

void Citire ()
{
    ifstream fin ("strmatch.in");
    fin >> (B + 1) >> (A + 1);
    N = strlen (A + 1);
    M = strlen (B + 1);
    fin.close ();
}

void Precalculare ()
{
    Pi[1] = 0;
    int p = 0;
    for (int i = 2; i <= M; i++)
    {
        for (; B[i] != B[p + 1] && p > 0;) p = Pi[p];
        if (B[i] == B[p + 1]) p++;
        Pi[i] = p;
    }
}

void Business ()
{
    int p = 0;
    for (int i = 1; i <= N; i++)
    {
        for (; A[i] != B[p + 1] && p > 0;) p = Pi[p];
        if (A[i] == B[p + 1]) p++;
        if (p == M)
        {
            if (cnt < 1000) v[cnt] = i - M;
            cnt++;
            p = Pi[p];
        }
    }
}

void Scriere ()
{
    ofstream fout ("strmatch.out");
    fout << cnt << "\n";
    cnt = min (cnt, 1000);
    for (int i = 0; i < cnt; i++)
        fout << v[i] << " ";
    fout.close ();
}

int main ()
{
    Citire ();
    Precalculare ();
    Business ();
    Scriere ();
    return 0;
}