Cod sursa(job #1809250)

Utilizator delia_ioanaCeapa Delia Ioana delia_ioana Data 18 noiembrie 2016 19:12:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#define N_MAX 2000002
using namespace std;

#define P 73
#define MOD1 100007
#define MOD2 100021

char a[N_MAX], b[N_MAX];
vector<int> sol;
int hash_a1 = 0, hash_b1 = 0, hash_a2 = 0, hash_b2 = 0;
bool flag = true;

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

    if (strlen(b) < strlen(a)) {
        printf("0");
        return 0;
    }

    fgets(a, N_MAX, stdin);
    a[strlen(a) - 1] = '\0';
    fgets(b, N_MAX, stdin);
    b[strlen(b) - 1] = '\0';

    int n1 = strlen(a), n2 = strlen(b);

    for (int i = 0; i < n1; i ++) {
        hash_a1 = (P * hash_a1) % MOD1 + a[i];
        hash_b1 = (P * hash_b1) % MOD1 + b[i];
	hash_a2 = (P * hash_a2) % MOD2 + a[i];
        hash_b2 = (P * hash_b2) % MOD2 + b[i];
    }

    if (hash_a1 == hash_b1 && hash_a2 == hash_b2)
        sol.push_back(0);

    int pw1 = 1, pw2 = 1;
    for (int i = 0; i < n1 - 1; i ++) {
	pw1 = (pw1 * P) % MOD1; 
	pw2 = (pw2 * P) % MOD2; 
    }

    for (int i = n1; i < n2; i ++) {
        hash_b1 = (P * ((hash_b1 - b[i - n1] * pw1) % MOD1 + MOD1) + b[i]) % MOD1;
        hash_b2 = (P * ((hash_b2 - b[i - n1] * pw2) % MOD2 + MOD2) + b[i]) % MOD2;
        if (hash_a1 == hash_b1 && hash_a2 == hash_b2) {
            sol.push_back(i - n1 + 1);
        }
    }

    printf("%d\n", sol.size());
    for (int i = 0; i < min(1000, (int)sol.size()); i ++)
        printf("%d ", sol[i]);
    printf("\n");

    return 0;
}