Cod sursa(job #1969437)

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

#define MAX_LGH 2000005

FILE* fin;
FILE* fout;

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

int pi[MAX_LGH] = { 0 };

int n;
int m;

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

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

void Init()
{
    LoadFiles();
}

void Read()
{
    fscanf(fin, "%s", a);
    fscanf(fin, "%s", b);

    n = strlen(a);
    m = strlen(b);
}

void Prefix()
{
    int k = 0;
    pi[0] = 0;

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

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

        pi[i] = k;
    }
}

void Find()
{
    int k = 0;

    for(int i=0;i<m;i++)
    {
        if(b[i] == a[k])
        {
            k++;
            if(k == n)
            {
                lengths[lghCount++] = i - n+1;
                while(k != pi[k] && b[i] != a[k])
                {
                    k = pi[k];
                }
                i--;
            }
        }
        else
        {
            while(k != pi[k] && b[i] != a[k])
            {
                k = pi[k];
            }

            if(b[i] == a[k])
            {
                k++;
                if(k == n)
                {
                    lengths[lghCount] = i -n + 1;
                    while(k != pi[k] && b[i] != a[k])
                    {
                        k = pi[k];
                    }

                    i--;
                }
            }
        }
    }
}

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

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

    for(int i=0;i<lghCount;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;
}