Cod sursa(job #1998325)

Utilizator Horia14Horia Banciu Horia14 Data 7 iulie 2017 14:38:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<cstring>
using namespace std;

#define MAX_LEN 2000000
#define MOD1 100007
#define MOD2 100021
#define base 73
#define MAX_POS 1000

char P[MAX_LEN + 1], T[MAX_LEN + 1];
int n, m, k, hashP1, hashP2, hashT1, hashT2, H1, H2;
int pos[MAX_POS];

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

int main()
{
    int i, nr;
    FILE *fin, *fout;
    fin = fopen("strmatch.in","r");
    fout = fopen("strmatch.out","w");
    fscanf(fin,"%s%s",P,T);
    m = strlen(P);
    n = strlen(T);
    H1 = H2 = 1;
    for(i=0; i<m; i++)
    {
        hashP1 = (hashP1 * base + P[i]) % MOD1;
        hashP2 = (hashP2 * base + P[i]) % MOD2;

        hashT1 = (hashT1 * base + T[i]) % MOD1;
        hashT2 = (hashT2 * base + T[i]) % MOD2;

        if(i)
        {
            H1 = (H1 * base) % MOD1;
            H2 = (H2 * base) % MOD2;
        }
    }
    for(i=0; i<=n-m; i++)
    {
        if((hashP1 == hashT1) && (hashP2 == hashT2))
        {
            if(k < MAX_POS)
                pos[k++] = i;
            else k++;
        }
        hashT1 = ((hashT1 - (T[i] * H1) % MOD1 + MOD1) * base + T[i+m]) % MOD1;
        hashT2 = ((hashT2 - (T[i] * H2) % MOD2 + MOD2) * base + T[i+m]) % MOD2;
    }
    nr = minim(k,MAX_POS);
    fprintf(fout,"%d\n",k);
    for(i=0; i<nr; i++)
        fprintf(fout,"%d ",pos[i]);
    if(k)
        fprintf(fout,"\n");
    fclose(fin);
    fclose(fout);
    return 0;
}