Cod sursa(job #2277234)

Utilizator razvanlgu31Razvan Lungu razvanlgu31 Data 5 noiembrie 2018 21:32:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstring>
#define NMAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i, j, pi[NMAX], lenA, lenB, q, poz[NMAX], nr;
char A[NMAX], B[NMAX];
void prefix() {
    q = 0;
    pi[1] = 0;
    for (i = 2; i <= lenA; i++) {
        while(q && A[i] != A[q + 1])
            q = pi[q];
        if(A[i] == A[q + 1])
            q++;
        pi[i] = q;
    }
}
int main()
{
    fin.getline(A, NMAX);
    fin.getline(B, NMAX);
    lenA = strlen(A);
    lenB = strlen(B);
    for (i = lenA; i >= 1; i--)
        A[i] = A[i - 1];
    A[0] = ' ';
    for (i = lenB; i >= 1; i--)
        B[i] = B[i - 1];
    B[0] = ' ';
    prefix();
    q = 0;
    for (i = 1; i <= lenB; i++) {
        while(q && A[q + 1] != B[i])
            q = pi[q];
        if(A[q + 1] == B[i])
            q++;
        if(q == lenA) {
            q = pi[lenA];
            nr++;
            if(nr <= 1000)
                poz[nr] = i - lenA;
        }
    }
    fout << nr << '\n';
    for(i = 1; i <= nr && i <= 1000; i++)
        fout << poz[i] << " ";

    return 0;
}