Cod sursa(job #1434445)

Utilizator retrogradLucian Bicsi retrograd Data 10 mai 2015 17:05:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<iostream>
#include<cstdio>

using namespace std;
typedef int var;

#define P 9901

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

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

    scanf("%s", &pattern);
    scanf("%s", &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];
    }

    printf("%d\n", no);
    if(no > 1000) no = 1000;

    for(var i=1; i<=no; i++)
        printf("%d ", Sol[i]);

}