Cod sursa(job #1434421)

Utilizator retrogradLucian Bicsi retrograd Data 10 mai 2015 16:46:38
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;
typedef int var;

#define P 209141

char pattern[3000000], Text[3000000];
var Sol[5000];

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

    cin>>pattern;
    cin>>Text;

    var pH = 0, l = 0, power = 1;

    for(var i=0; pattern[i]; i++) {
        l++;
        pH = pH * P + pattern[i];
    }

    var has = 0;
    var i;
    for(i=0; i<l-1; i++) {
        power *= P;
        has = has * P + Text[i];
    }

    var no = 0;

    for(;Text[i]; i++) {
        has = has * P + Text[i];
        if(has == pH) {
            no++;
            if(no <= 1000)
                Sol[no] = i-l+1;
        }
        has -= power * Text[i-l+1];
    }

    cout<<no<<'\n';
    if(no > 1000) no = 1000;

    for(var i=1; i<=no; i++)
        cout<<Sol[i]<<" ";

}