Cod sursa(job #2028407)

Utilizator Horia14Horia Banciu Horia14 Data 27 septembrie 2017 21:06:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<cstring>
#define MAX_LEN 2000000
#define MAX_POS 1000
using namespace std;

char P[MAX_LEN+1], T[MAX_LEN+1];
int pi[MAX_LEN], pos[MAX_POS], n, m, nr;

inline int minim(int x, int y)
{
    if(x < y) return x;
    return y;
}

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

void buildPrefix()
{
    int k = 0;
    for(int i=1; i<m; i++)
    {
        while(k > 0 && P[i] != P[k])
            k = pi[k-1];
        if(P[i] == P[k])
            k++;
        pi[i] = k;
    }
}

void KMP()
{
    int k = 0;
    for(int i=0; i<n; i++)
    {
        while(k > 0 && T[i] != P[k])
            k = pi[k-1];
        if(T[i] == P[k])
            k++;
        if(k == m)
        {
            if(nr < MAX_POS)
                pos[nr++] = i - m + 1;
            else nr++;
        }
    }
}

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

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