Cod sursa(job #1563421)

Utilizator serbanSlincu Serban serban Data 6 ianuarie 2016 00:29:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

#define key2 100007
#define key1 100021
#define fact 101

using namespace std;

char a[2000005]; int n;
char b[2000005]; int m;
long long hA1, hA2, hB1, hB2, for1 = 1, for2 = 1; int nr;
vector<int> ret;

int main()
{
    FILE *f = fopen("strmatch.in", "r");
    FILE *g = fopen("strmatch.out", "w");
    fscanf(f, "%s", &a); n = strlen(a);
    fscanf(f, "%s", &b); m = strlen(b);
    if(n > m) {fprintf(g, "0\n"); return 0;}
    for(int i = 0; i < n; i ++) {
        hA1 = (hA1 * fact + a[i]) % key1;
        hA2 = (hA2 * fact + a[i]) % key2;
        if(i) {
            for1 = (for1 * fact) % key1;
            for2 = (for2 * fact) % key2;
        }
    }

    for(int i = 0; i < n; i ++) {
        hB1 = (hB1 * fact + b[i]) % key1;
        hB2 = (hB2 * fact + b[i]) % key2;
    }

    if(hA1 == hB1 && hA2 == hB2) {
        nr ++;
        ret.push_back(0);
    }

    for(int i = n; i < m; i ++) {
        hB1 = ((hB1 - (b[i - n] * for1) % key1 + key1) * fact + b[i]) % key1;
        hB2 = ((hB2 - (b[i - n] * for2) % key2 + key2) * fact + b[i]) % key2;
        if(hA1 == hB1 && hA2 == hB2) {
            nr ++;
            ret.push_back(i - n + 1);
        }
    }

    fprintf(g, "%d\n", nr);
    for(int i = 0; i < ret.size() && i < 1000; i ++) {
        fprintf(g, "%d ", ret[i]);
    }
    fprintf(g, "\n");
    return 0;
}