Cod sursa(job #632498)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 11 noiembrie 2011 13:24:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<cstdio>
#include<string.h>
#define N 2000005
#define MOD 1299709
#define BASE 62
char sir[255];
int contor;
char a[N];
int result[1005];
char b[N];
int ok;
long long t;
int NA, NB;
int powb;
long long str;

int modulus(int a, int b) {
    while(a >= b)
     a -= b;
    return a;
}
void init() {
    powb = 1;
    for(int i = 1; i < NA; i++)
     powb = modulus((powb * BASE), MOD);
    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 main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&a);
    scanf("%s",&b);
    NA = strlen(a);
    NB = strlen(b);
    init();
    for(int i = 0; i < NA; i++) {
        t = modulus(modulus((t * BASE), MOD)  + sir[a[i]], MOD);
        str = modulus(modulus((str * BASE), MOD)  + sir[b[i]], MOD);
    }
    for(int i = 1; i <= NB - NA + 1; i++) {
        str = modulus(modulus(((str - powb * sir[b[i-1]]) * BASE),MOD) + sir[b[i + NA - 1]], MOD);
        if(str == t) {
            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;
            }

        }
    }
    printf("%d\n",contor);
    for(int i = 1; i <= contor; i++)
     printf("%d ", result[i]);
    return 0;
}