Cod sursa(job #1267446)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 19 noiembrie 2014 21:44:14
Problema Potrivirea sirurilor Scor 36
Compilator c Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <ctype.h>
 
#define N_MAX 2000000
#define MOD 1234567891
#define P 666013
 
char A[N_MAX + 2], B[N_MAX + 2];
int M, N, buff[N_MAX + 1], sp;
unsigned long long checksum, pwr = 1;
 
void read(FILE *fin)
{
    while (isalnum(A[++M] = fgetc(fin))); // M cu 1 mai mare
    while (isalnum(B[++N] = fgetc(fin))); // N cu 1 mai mare
}
 
void prec()
{
    int i;
    for (i = 1; i < M; i++) {
        pwr = (pwr * P) % MOD;
        checksum = (checksum * P + A[i]) % MOD;
    }
}
 
void rk()
{
    int i;
    unsigned long long curr = 0;
    for (i = 1; i < N; i++) {
        if (curr == checksum && sp <= 1000) {
            buff[++sp] = i - M;
        }
        curr = (curr * P + B[i] - (i >= M ? B[i - M + 1] * pwr : 0)) % MOD;
    }
}
 
void print(FILE *fout)
{
    int i;
    fprintf(fout, "%d\n", sp);
    for (i = 1; i <= sp; i++) {
        fprintf(fout, "%d ", buff[i]);
    }
}
 
int main()
{
    FILE *fin, *fout;
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");
     
    read(fin);
    prec();
    rk();
    print(fout);
     
    //printf("%s%d\n%s%d", A + 1, M, B + 1, N);
     
    fclose(fin);
    fclose(fout);
    return 0;
}