Cod sursa(job #1659749)

Utilizator mateibanuBanu Matei Costin mateibanu Data 22 martie 2016 16:06:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <string.h>
#define mx 2000010
using namespace std;

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

long pi[mx+1],v[1024],i,h,n,m,p;
char s1[mx+10],s2[mx+10];

void prefix()
{
    p=0;
    for (i=2;i<=n;i++)
    {
        while (p>0&&s1[i]!=s1[p+1])
            p=pi[p];
        if (s1[i]==s1[p+1])
            p++;
        pi[i]=p;
    }
}

void kmp()
{
    p=0;
    h=0;
    for (i=1;i<=m;i++)
    {
        while (p>0&&s2[i]!=s1[p+1])
            p=pi[p];
        if (s2[i]==s1[p+1]) p++;
        if (p==n)
        {
            p=pi[p];
            h++;
            if (h<=1000)
                v[h]=i-n;
        }
    }
}

int main()
{
    fgets(s1+1,mx,f);
    fgets(s2+1,mx,f);
    n=strlen(s1+1)-1;
    m=strlen(s2+1)-1;
    prefix();
    kmp();
    if (h>1000) h=1000;
    fprintf(g,"%ld\n",h);
    for (i=1;i<=h;i++) fprintf(g,"%ld ",v[i]);
    fclose(g);
    fclose(f);
    return 0;
}