Cod sursa(job #632831)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 12 noiembrie 2011 13:34:56
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include<cstdio>
#include<string.h>
#define N 2000005
#define MOD1 7368787
#define MOD2 7368791
#define BASE 62
int contor;
char a[N];
int sir[256];
int result[1005];
char b[N];
int ok;
int t, t2;
int NA, NB;
int powb, powc;
int str, str2;

void init() {
    powb = 1;
    powc = 1;
    for(int i = 1; i < NA; i++) {
     powb = (powb * BASE) % MOD1;
     powc = (powc * BASE) % MOD2;
    }
    for(char i = 'A'; i <= 'Z'; i++)
     sir[i] = i - 'A';
    for(char i = 'a'; i <= 'z'; i++)
     sir[i] = i - 'a' + 26;
    for(char i = '0'; i <= '9'; i++)
     sir[i] = i - '0' + 52;
    return;
}
int minim(int a, int b) {
    if(a < b) return a;
    return b;
}
int checkeq(int i) {
    ok = 1;
    for(int j = i; j < i + NA; j++)
       if(b[j] != a[j - i]) ok = 0;
         if(ok == 1) {
            contor++;
            if (contor <= 1000)
                result[contor] = i;
        }
}
int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",&a, &b);
    NA = strlen(a);
    NB = strlen(b);
    init();
    for(int i = 0; i < NA; i++) {
        t = (t * BASE + sir[a[i]]) % MOD1;
        t2 = (t2 * BASE + sir[a[i]]) % MOD2;
        str = (str * BASE  + sir[b[i]]) % MOD1;
        str2 = (str2 * BASE  + sir[b[i]]) % MOD2;
    }
    if((str == t) && (str2 == t2))
     checkeq(0);
    for(int i = 1; i <= NB - NA + 1; i++) {
        str = ((str - (powb * sir[b[i-1]]) % MOD1 + MOD1) * BASE + sir[b[i + NA - 1]]) % MOD1;
        str2 = ((str2 - (powc * sir[b[i-1]]) % MOD2 + MOD2) * BASE + sir[b[i + NA - 1]]) % MOD2;
        if((str == t) && (str2 == t2))
            checkeq(i);
    }
    printf("%d\n",contor);
    for(int i = 1; i <= minim(contor, 1000); i++)
     printf("%d ", result[i]);
    return 0;
}