Cod sursa(job #2288926)

Utilizator danin01Nastase Daniel danin01 Data 24 noiembrie 2018 09:39:58
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;

FILE*f=fopen("strmatch.in","r");
FILE*g = fopen("strmatch.out","w");

char A[2000002],B[2000002];

int k=0;

vector<int>poz;

int P[2000002];

int main()
{
    fscanf(f,"%s",A+1);
    fscanf(f,"%s",B+1);

    if(strlen(A+1)>strlen(B+1))
    {
        fprintf(g,"0");
        return 0;
    }

    for(int i=2;i<=strlen(A+1);++i)
    {

        for(;k>0 && A[k+1]!=A[i];)k=P[k];
        if(A[k+1]==A[i])k++;
        P[i]=k;

    }

    for(int i=1;i<=strlen(B+1);++i)
    {

       for(;k!=0 && A[k+1]!=B[i];)k=P[k];
       if(A[k+1]==B[i])k++;
       if(k==strlen(A+1))
       {
            poz.push_back(i-strlen(A+1));
            k=P[k];
       }

    }

    fprintf(g,"%d\n",poz.size());

    for(int i=0;i<poz.size() && i<1000;++i)
    {
        fprintf(g,"%d ",poz[i]);
    }

    return 0;
}