Cod sursa(job #2364725)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 4 martie 2019 10:39:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#define N 2000004
#include <cstring>
#include <iostream>

using namespace std;
FILE *f,*g;

char c1[N],c2[N];
int lg1,lg2,pi[N],sol,v[1002];

void kmp()
{
    int k=0;
    for(int i=1;i<=lg2;++i)
    {
        while(k && c1[k+1]!=c2[i])
            k=pi[k];
        if(c1[k+1]==c2[i])
            ++k;
        if(k==lg1)
        {
            if(sol<1000)
                v[++sol]=i;
            else
                ++sol;
        }
    }
}
void kmp1()
{
    int k=0;
    for(int i=2;i<=lg1;++i)
    {
        while(k && c1[k+1]!=c1[i])
            k=pi[k];
        if(c1[k+1]==c1[i])
            ++k;
        pi[i]=k;
    }
}
int main()
{
    f=fopen("strmatch.in","r");
    g=fopen("strmatch.out","w");
    fgets(c1+1,N,f);
    fgets(c2+1,N,f);
    lg1=strlen(c1+1);
    c1[lg1]=NULL;
    --lg1;
    lg2=strlen(c2+1);
    c2[lg2]=NULL;
    --lg2;
    kmp1();
    kmp();
    fprintf(g,"%d\n",sol);
    sol=min(sol,1000);
    for(int i=1;i<=sol;++i)
        fprintf(g,"%d ",v[i]-lg1);
    fclose(f);
    fclose(g);
    return 0;
}