Cod sursa(job #2084090)

Utilizator leraValeria lera Data 8 decembrie 2017 17:24:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define Nmax 2000005

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int p = 127;

long long hash1, hash2, p2 = 1;
vector<int>sol;
int n, m;
char a[Nmax], b[Nmax];
int main()
{
    fin >> a;
    fin >> b;
    n = strlen(a);
    m = strlen(b);
    hash1 = 0;
    hash2 = 0;
    for(int i = 0; i < n; i++)
        hash1 = hash1 * p + a[i];
    for(int i = 0; i < n; i++)
        hash2 = hash2 * p + b[i];

    for(int i = 1; i < n; i++)
        p2 = p2 * p;
    if(hash1 == hash2)sol.push_back(0);
    for(int i = n; i < m; i++)
    {
        hash2 -= p2 * b[i - n];
        hash2 = hash2 * p + b[i];
        if(hash1 == hash2)sol.push_back(i - n + 1);
    }
    fout << sol.size() << '\n';
    for(int i = 0 ; i < sol.size() && i < 1000; i++)
        fout << sol[i] << " ";
    return 0;
}