Cod sursa(job #1344253)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 16 februarie 2015 15:55:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>
#define DIM 2000010

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

char A[DIM], B[DIM];
int P[DIM], n, m, i, j, S[DIM], lenght, nr;

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

    P[1] = 0;
    lenght = 0;

    for(i = 2; i <= n; i ++)
        {
            while(lenght && A[lenght + 1] != A[i])
                lenght = P[lenght];

            if(A[lenght + 1] == A[i])
                lenght ++;

         P[i] = lenght;
        }

    lenght = 0;
    for(i = 1; i <= m; i ++)
        {
            while(lenght && A[lenght + 1] != B[i])
                lenght = P[lenght];

            if(A[lenght + 1] == B[i])
                lenght ++;

            if(lenght == n)
            {
                nr ++;
                if(nr <= 1000)
                    S[nr] = i - lenght + 1;
                lenght = P[lenght];
            }
        }
    fout << nr << '\n';
    if(nr > 1000)
        nr = 1000;
    for(i = 1; i <= nr; i ++)
        fout << S[i] - 1 << " ";
    return 0;
}