Cod sursa(job #2349508)

Utilizator Robys01Robert Sorete Robys01 Data 20 februarie 2019 15:32:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000005
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int v[NMAX], n, m, nr;
char A[NMAX], B[NMAX];
vector <int> answer;

void prefix(){
    int k = 0;
    v[1] = 0;

    for(int i=2; i<=n; i++){

        while(k && B[k+1] != B[i])
            k = v[k];

        if(B[k+1] == B[i])
            k++;
        v[i] = k;

    }
}

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

    prefix();

    int k = 0;
    for(int i=1; i<=m; i++){

        while(k && B[k+1] != A[i])
            k = v[k];

        if(B[k+1] == A[i])
            k++;
        if(k==n){
            nr++;
            k = v[k];
            answer.push_back(i-n);
        }

    }
   cout<<nr<<'\n';
   int size;
   if(answer.size() > 1000)
        size = 1000;
    else
        size = answer.size();

   for(size_t i = 0; i<size; i++)
        cout<<answer[i]<<' ';


    return 0;
}