Cod sursa(job #1434443)

Utilizator retrogradLucian Bicsi retrograd Data 10 mai 2015 17:04:24
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<iostream>
#include<cstdio>

using namespace std;
typedef int var;

var P;

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

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(char i='a'; i<='z'; i++) {
        Map[i] = P++;
        Map[i-'a'+'A'] = P++;
    }

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

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

    var no = 0;

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

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

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

}