Cod sursa(job #2093070)

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

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

void citire()
{
    fgets(x+1,2000001,f);
    fgets(y+1,2000001,f);
    fgets(y+1,2000001,f);
    m=strlen(x+1)-1;
    n=strlen(y+1)-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++;
        if(k==m)
        {
            ss++;
            if(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;
}