Cod sursa(job #1780543)

Utilizator robertstrecheStreche Robert robertstreche Data 16 octombrie 2016 12:52:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <cstring>
#include <vector>

#define LMAX 2000001

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector <int >sol;

int k,nrsol,p[LMAX];
char A[LMAX],B[LMAX];


int main()
{
    f>>(A+1)>>(B+1);
    int lA=strlen(A+1);
    int lB=strlen(B+1);

    for (int i=2;i<=lA;i++){
        while (A[i]!=A[k+1] && k)k=p[k];
        if (A[i]==A[k+1])k++;
        p[i]=k;
    }

    k=0;
    for (int i=1;i<=lB;i++){
        while (B[i]!=A[k+1] && k)k=p[k];

        if (B[i]==A[k+1])k++;
        if (k==lA)nrsol++;
        if (nrsol<=1000 && k==lA)sol.push_back(i-lA);
    }
    g<<nrsol<<'\n';
    for (auto it:sol)g<<it<<' ';

}