Cod sursa(job #1954031)

Utilizator dumbraveanbDumbravean Bogdan dumbraveanb Data 5 aprilie 2017 10:12:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define Nmax 2000005

int n, m, Prfx[Nmax], Sol[1005], k;
char A[Nmax], B[Nmax];

void Prefix() {
    int q = 0;
    for(int i = 2; i <= n; ++i) {
        while(q && A[q + 1] != A[i])
            q = Prfx[q];
        if(A[q + 1] == A[i])
            ++q;
        Prfx[i] = q;
    }
}

int main()
{
    fin >> A + 1;
    fin >> B + 1;
    A[0] = B[0] = ' ';
    n = strlen(A + 1);
    m = strlen(B + 1);

    Prefix();

    int q = 0;
    for(int i = 1; i <= m; ++i) {
        while(q && A[q + 1] != B[i])
            q = Prfx[q];
        if(A[q + 1] == B[i])
            ++q;
        if(q == n) {
            q = Prfx[n];
            ++k;
            if(k <= 1000)
                Sol[k] = i - n;
        }
    }

    fout << k << '\n';
    for(int i = 1; i <= min(1000, k); ++i)
        fout << Sol[i] << ' ';
    return 0;
}