Cod sursa(job #1182837)

Utilizator lorundlorund lorund Data 7 mai 2014 21:24:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define SIZE 2000005
#define MOD 165191021
using namespace std;

char a[SIZE], b[SIZE];
unsigned la, lb, hashv, rhashv, pow=1;
vector<int> sol;

void solve();

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s %s", a, b);
    la = strlen(a);
    lb = strlen(b);

    if (la>lb){
        return 0;
    }
    solve();
    printf("%d\n", sol.size());
    for (unsigned i=0; i<sol.size(); ++i){
        printf("%d ", sol[i]);
    }
    return 0;
}

void solve(){
    for (unsigned i=0; i<la; ++i){
        hashv = (hashv*27+a[i]-'A'+1)%MOD;
        pow = pow*27%MOD;
    }
    pow /= 27;

    for (unsigned i=0; i<la; ++i){
        rhashv = (rhashv*27+b[i]-'A'+1)%MOD;
    }

    for (unsigned i=la; i<=lb; ++i){
        if (hashv==rhashv && !memcmp(a, &b[i-la], la)){
            sol.push_back(i-la);
            if (sol.size()>=1000)
                return;
        }
        rhashv = (rhashv+MOD-pow*(b[i-la]-'A'+1))%MOD;
        rhashv = (rhashv*27+b[i]-'A'+1)%MOD;
    }
}