Cod sursa(job #1816449)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 26 noiembrie 2016 15:02:16
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
//
//  main.cpp
//  Rabin-Karp
//
//  Created by Albastroiu Radu on 11/26/16.
//  Copyright © 2016 Albastroiu Radu. All rights reserved.
//

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cstring>
#include <cmath>

#define BASE 27
#define HASH07 100007
#define HASH09 100021

using namespace std;

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

int size;
long long first_hash_07, first_hash_09, second_hash_07, second_hash_09, power_mod_07, power_mod_09;
string a, b;
vector<int> positions;

// BASE ^ power
void compute_power(int power, long long& mod)
{
    long long base = BASE;
    long long sol = 1;
    while(power)
    {
        if(power % 2)
        {
            sol = sol * base % mod;
        }
        power = power / 2;
        base = base * base % mod;
    }
    mod = sol % mod;
}

// 'aba' -> 'abac'
void add_back(int nr_add, long long& mod_07, long long& mod_09)
{
    mod_07 *= BASE;
    mod_07 += nr_add;
    mod_07 %= HASH07;
    
    mod_09 *= BASE;
    mod_09 += nr_add;
    mod_09 %= HASH09;
}

// 'aba' -> 'ba'
void pop_front(int nr_pop, int power, long long& mod_07, long long& mod_09)
{
    long long nr_mod_07 = power_mod_07;
    long long nr_mod_09 = power_mod_09;
    
    nr_mod_07 *= nr_pop;
    nr_mod_09 *= nr_pop;
    
    nr_mod_07 %= HASH07;
    nr_mod_09 %= HASH09;
    
    mod_07 = mod_07 - nr_mod_07 + HASH07;
    mod_07 %= HASH07;

    mod_09 = mod_09 - nr_mod_09 + HASH09;
    mod_09 %= HASH09;
}

int main()
{
    
    fin >> a;
    fin >> b;
    
    power_mod_07 = HASH07;
    power_mod_09 = HASH09;
    
    compute_power( int(a.size() - 1), power_mod_07);
    compute_power( int(a.size() - 1), power_mod_09);

    for (int i = 0; i < a.size(); i++)
        add_back(a[i] - 'A' + 1, first_hash_07, first_hash_09);
    
    for (int i = 0; i < b.size(); i++)
    {
        if(size < a.size())
        {
            size++;
            add_back(b[i] - 'A' + 1, second_hash_07, second_hash_09);
        }
        
        if(size == a.size())
        {
            if(first_hash_07 == second_hash_07 &&
               first_hash_09 == second_hash_09)
            {
                positions.push_back(i - size + 1);
                if(positions.size() == 1000)
                    break;
            }
            
            size --;
            pop_front(b[i - size] - 'A' + 1, size, second_hash_07, second_hash_09);
        }
    }
    
    fout << positions.size() << "\n";
    for (int i = 0; i < positions.size(); i++)
        fout << positions[i] << " ";
    
    return 0;
}