Cod sursa(job #1184197)

Utilizator lorundlorund lorund Data 11 mai 2014 17:25:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#define SIZE 2000005
#define MOD 68174081
using namespace std;

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

void solve();
void init();

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){
        printf("0\n");
        return 0;
    }
    init();
    solve();
    printf("%d\n", sol.size());
    for (unsigned i=0; i<sol.size() && i<1000; ++i){
        printf("%d ", sol[i]);
    }
    return 0;
}

void init(){
    for (char c='0'; c<='9'; ++c)
        code[c] = size++;
    for (char c='A'; c<='Z'; ++c)
        code[c] = size++;
    for (char c='a'; c<='z'; ++c)
        code[c] = size++;
}

void solve(){
    for (unsigned i=0; i<la; ++i){
        hashv = (hashv*size+code[a[i]])%MOD;
        rhashv = (rhashv*size+code[b[i]])%MOD;
    }
    for (unsigned i=1; i<la; ++i){
        pow = pow*size%MOD;
    }

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