Cod sursa(job #1786150)

Utilizator delia_ioanaCeapa Delia Ioana delia_ioana Data 22 octombrie 2016 14:58:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <math.h>
#define N_MAX 2000002
using namespace std;

char a[N_MAX], b[N_MAX];

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

    vector<int> sol;
    if (strlen(b) < strlen(a)) {
        printf("0");
        return 0;
    }

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

    int prim = 3, hash_a = 0, hash_b = 0;
    bool flag = true;

    for (int i = 0; i < strlen(a); i ++) {
        hash_a += pow(prim, i) * a[i];
        hash_b += pow(prim, i) * b[i];
        if (a[i] != b[i])
            flag = false;
    }

    if (hash_a == hash_b && flag)
        sol.push_back(0);

    for (int i = strlen(a); i < strlen(b); i ++) {
        hash_b -= b[i - strlen(a)];
        hash_b /= prim;
        hash_b += pow(prim, strlen(a) - 1) * b[i];
        if (hash_a == hash_b) {
            flag = true;
            for (int j = 0; j < strlen(a); j ++)
                if (a[j] != b[i - strlen(a) + 1 + j])
                    flag = false;
            if (flag)
                sol.push_back(i - strlen(a) + 1);
        }
    }

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

    return 0;
}