Cod sursa(job #1969491)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 18 aprilie 2017 14:54:06
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <string.h>

#define MAX_LGH 2000005

FILE* fin;
FILE* fout;

char a[MAX_LGH] = { 0, 0 };
char b[MAX_LGH] = { 0, 0 };

int pi[MAX_LGH] = { 0, 0 };

int n;
int m;

int lengths[MAX_LGH] = { 0 };
int crtLgh = 0;

void LoadFiles()
{
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");
}

void Init()
{
    LoadFiles();
}

void Read()
{
    fscanf(fin, "%s", &a[1]);
    fscanf(fin, "%s", &b[1]);

    n = strlen(&a[1]);
    m = strlen(&b[1]);
}

void Prefix()
{
    int k = 0;

    pi[1] = 0;

    for(int i=2;i<=n;i++)
    {
        while(k > 0 && a[k+1] != a[i])
        {
            k = pi[k];
        }

        if(a[k+1] == a[i])
        {
            k++;
        }

        pi[i] = k;
    }
}

void KMP()
{
    int k = 0;

    for(int i=1;i<=m;i++)
    {
        while(k > 0 && b[i] != a[k+1])
        {
            k = pi[i];
        }

        if(b[i] == a[k+1])
        {
            k++;
        }

        if(k == n)
        {
            k = pi[n];

            //printf("%d\n", i);
            if(crtLgh < 1000)
            {
                lengths[crtLgh++] = i - n;
            }
        }
    }
}

void Solve()
{
    Prefix();
    KMP();
}

void Write()
{
    fprintf(fout, "%d\n", crtLgh);

    for(int i=0;i<crtLgh;i++)
    {
        fprintf(fout, "%d ", lengths[i]);
    }
}

void CloseFiles()
{
    fclose(fin);
    fclose(fout);
}

void Terminate()
{
    CloseFiles();
}

int main(void)
{
    Init();
    Read();
    Solve();
    Write();
    Terminate();

    return 0;
}