Cod sursa(job #1838650)

Utilizator Horia14Horia Banciu Horia14 Data 1 ianuarie 2017 15:44:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<cstring>
#define NMAX 2000005
#define LMAX 1002
using namespace std;

char A[NMAX], B[NMAX];
int L[NMAX], s[LMAX], n, m, nr;

void Read()
{
    FILE *fin = fopen("strmatch.in","r");
    fscanf(fin,"%s",A+1);
    fscanf(fin,"%s",B+1);
    m = strlen(A+1);
    n = strlen(B+1);
    fclose(fin);
}

void build_Prefix()
{
    int i, k;
    L[1] = 0;
    for(i=2; i<=m; i++)
    {
        k = L[i-1];
        while(k > 0 && A[k+1] != A[i])
            k = L[k];
        if(A[k+1] == A[i])
            k++;
        L[i] = k;
    }
}

void KMP()
{
    int i, k;
    k = 0;
    for(i=1; i<=n; i++)
    {
        while(k > 0 && A[k+1] != B[i])
            k = L[k];
        if(A[k+1] == B[i])
            k++;
        if(k == m)
        {
            nr++;
            if(nr <= 1000)
                s[nr] = i-m;
            k = L[k];
        }
    }
}

int minim(int a, int b)
{
    if(a < b)
        return a;
    return b;
}

void Write()
{
    int i, l;
    FILE *fout = fopen("strmatch.out","w");
    l = minim(nr,1000);
    fprintf(fout,"%d\n",nr);
    for(i=1; i<=l; i++)
        fprintf(fout,"%d ",s[i]);
    fclose(fout);
}

int main()
{
    Read();
    build_Prefix();
    KMP();
    Write();
    return 0;
}