Cod sursa(job #2194933)

Utilizator AgacheGabrielAgache Gabriel AgacheGabriel Data 14 aprilie 2018 18:01:45
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <cstring>

using namespace std;

char text[2000010],pat[2000010];

FILE *fin,*fout;

int table[256],n,m,i,j,sol[1010],nrSol;

int maxi(int a, int b)
{
    return a>b ? a:b;
}

int mini(int a, int b)
{
    return a<b ? a:b;
}

void read()
{
    fin = fopen("strmatch.in","r");
    fout = fopen("strmatch.out","w");
    fscanf(fin,"%s",pat);
    fscanf(fin,"%s",text);
}

void preProces(char* pat)
{
    int len = m;
    for (int i = 0; i<len ; i++)
    {
        table[pat[i]] = maxi(1,len-i-1);
    }
}

void BM()
{
    int nextstep = 0;
    for (int i=0;i<=n-m-1;i+=nextstep)
    {
        nextstep = 0;
        for (int j = m-1;j>=0;j--)
        {
            if (text[i+j]!=pat[j])
            {
                if (table[text[i+j]])
                {
                    nextstep = table[text[i+j]];
                    break;
                }
                else
                {
                    nextstep = j+1;
                    break;
                }
            }
        }
        if (!nextstep)
        {
            nrSol++;
            nextstep = 1;
            if (nrSol<=1000)
                sol[nrSol] = i;
        }
    }
}

int main()
{
    read();
    n = strlen(text);
    m = strlen(pat);
    preProces(pat);
    BM();
    fprintf(fout,"%d\n",nrSol);
    for (int i=1 ; i<=mini(nrSol,1000) ;i++ )
        fprintf(fout,"%d ",sol[i]);
    fprintf(fout,"\n");
    return 0;
}