Cod sursa(job #1106224)

Utilizator lehman97Dimulescu David lehman97 Data 12 februarie 2014 17:34:31
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

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


int urm[2000000],q,v[2000000],i,n,m;
char s1[2000000],s2[2000000];
void urmator(char s1[2000000])
{
    int k,i;
    k=-1;
    for(i=2;i<=m;i++)
    {
        while(k>0 && s1[i-1]!=s1[k+1])k=urm[k];
        if(s1[k+1]==s1[i-1]) k++;
        urm[i]=k+1;
    }
}

int main()
{
    fgets(s1,2000000,f);
    strcpy(s1+strlen(s1)-1,s1+strlen(s1));
    m=strlen(s1);
    fgets(s2,2000000,f);
    strcpy(s2+strlen(s2)-1,s1+strlen(s2));
    urmator(s1);
    n=strlen(s2);
    q=-1;
    for(i=1;i<=n;i++)
    {
        while(q>0 && s1[q+1]!=s2[i-1])q=urm[q+1]-1;
        if(s1[q+1]==s2[i-1]) q++;
        if(q==m-1)
        {
            v[++v[0]]=i-m;
        }
    }
    fprintf(g,"%d\n",v[0]);
    for(i=1;i<=v[0];i++)
    fprintf(g,"%d ",v[i]);

    return 0;
}