Cod sursa(job #1434419)

Utilizator retrogradLucian Bicsi retrograd Data 10 mai 2015 16:43:03
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];
vector<var> Sol;

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

    cin>>pattern;
    cin>>Text;

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

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

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

    for(;Text[i]; i++) {
        has = has * P + Text[i];
        if(has == patternH)
            Sol.push_back(i-l+1);
        has = has - power * Text[i-l+1];
    }

    cout<<Sol.size()<<'\n';
    var stop = Sol.size();
    if(stop > 1000) stop = 1000;

    for(var i=0; i<stop; i++)
        cout<<Sol[i]<<" ";

}