Cod sursa(job #1460223)

Utilizator retrogradLucian Bicsi retrograd Data 11 iulie 2015 21:17:21
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

#define B 9901
#define MAXN 2000005

int Sol[1005];
char p[MAXN], t[MAXN];

int main() {

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

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


    uint64_t h = 0;


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

    uint64_t mh = 0;
    for(int i=1; i<=l; i++) {
        mh = mh * B + t[i];
    }

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

        mh *= B;
        mh += t[i];
        mh -= t[i-l] * pw;
    }

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

    return 0;
}