Cod sursa(job #2093059)

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

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

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

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

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

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


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