Cod sursa(job #1460215)

Utilizator retrogradLucian Bicsi retrograd Data 11 iulie 2015 20:48:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

#define B 9901
#define MAXN 2000005
int64_t Part[MAXN], Pow[MAXN];
char t[MAXN], p[MAXN];

int64_t getHash(int e, int l) {
    return Part[e] - Part[e-l] * Pow[l];
}

int Sol[1005];

int main() {

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

    cin>>p;
    cin>>t+1;
    t[0] = '#';

    Pow[0] = 1;
    for(int i=1; t[i]; i++) {
        Part[i] = Part[i-1] * B + t[i];
        Pow[i] = Pow[i-1] * B;
    }

    int64_t h = 0;
    int l;
    for(l=0; p[l]; l++) {
        h = h * B + p[l];
    }

    int64_t nr = 0;
    for(int i=l; t[i]; i++) {
        if(getHash(i, l) == h) {
            nr++;
            if(nr <= 1000)
                Sol[nr] = i-l;
        }
    }

    cout<<nr<<'\n';
    for(int i=1; i<=nr && i <= 1000; i++) {
        cout<<Sol[i]<<" ";
    }

    return 0;
}