Cod sursa(job #2288938)

Utilizator danin01Nastase Daniel danin01 Data 24 noiembrie 2018 09:45:09
Problema Potrivirea sirurilor Scor 100
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,n,m;

vector<int>poz;

int P[2000002];

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

    n=strlen(A+1);
    m=strlen(B+1);

    if(n>m)
    {
        fprintf(g,"0");
        return 0;
    }

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

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

    }

    k=0;

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

       for(;k!=0 && A[k+1]!=B[i];)k=P[k];
       if(A[k+1]==B[i])k++;
       if(k==n)
       {
            poz.push_back(i-n);
            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;
}