Cod sursa(job #2093115)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 22 decembrie 2017 22:58:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <cstring>
using namespace std;
FILE *f,*g;

char x[2000002],y[2000002];
int n,m,ss,v[1004],pi[2000002];

void citire()
{
    fscanf(f,"%s",x);
    fscanf(f,"%s",y);
    m=strlen(x)-1;
    n=strlen(y)-1;
}

void kmp()
{
    int k=-1,i;
    pi[0]=-1;
    for(i=1;i<=m;i++)
    {
        while(k>-1&& x[k+1]!=x[i])
            k=pi[k];
        if(x[k+1]==x[i])
            k++;
        pi[i]=k;
    }
}

void kmp1()
{
    int i,k=-1;
    for(i=0;i<=n;i++)
    {
        while(k>-1 && x[k+1]!=y[i])
            k=pi[k];
        if(y[i]==x[k+1])
            k++;
        if(k==m)
        {
            ss++;
            if(ss<=1000)
                v[ss]=i-k;
        }
    }
}

void afisare()
{
    int i,mi=1000;
    /*for(i=1;i<=m;i++)
        fprintf(g,"%d ",pi[i]);
     fprintf(g,"\n");
    */
     fprintf(g,"%d\n",ss);
     if(ss<mi)
        mi=ss;
     for(i=1;i<=mi;i++)
       fprintf(g,"%d ",v[i]);
}


int main()
{
   f=fopen("strmatch.in","r");
   g=fopen("strmatch.out","w");
   citire();
   kmp();
   kmp1();
   afisare();
   fclose(f);
   fclose(g);
    return 0;
}