Pagini recente » Cod sursa (job #1522236) | Cod sursa (job #2611799) | Cod sursa (job #2949728) | Cod sursa (job #1912765) | Cod sursa (job #1816500)
//
// 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 77
#define HASH07 1000000007
#define HASH09 1000000009
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 = (mod_07 * BASE + nr_add) % HASH07;
mod_09 = (mod_09 * BASE + nr_add) % HASH09;
}
// 'aba' -> 'ba'
void pop_front(int nr_pop, long long& mod_07, long long& mod_09)
{
mod_07 = (mod_07 - (power_mod_07 * nr_pop) % HASH07 + HASH07) % HASH07;
mod_09 = (mod_09 - (power_mod_09 * nr_pop) % HASH09 + HASH09) % HASH09;
}
// 'abc' -> 'bcd'
void pop_add(int nr_pop, int nr_add, long long& mod_07, long long& mod_09)
{
mod_07 = ((mod_07 - (power_mod_07 * nr_pop) % HASH07 + HASH07) * BASE + nr_add) % HASH07;
mod_09 = ((mod_09 - (power_mod_09 * nr_pop) % HASH09 + HASH09) * BASE + nr_add) % 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);
power_mod_07 %= HASH07;
power_mod_09 %= HASH09;
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 < a.size(); i++)
add_back(b[i] - 'A' + 1, second_hash_07, second_hash_09);
if(first_hash_07 == second_hash_07 &&
first_hash_09 == second_hash_09)
positions.push_back(0);
for (int i = int(a.size()); i < b.size(); i++)
{
pop_add(b[i - a.size()] - 'A' + 1, b[i] - 'A' + 1, second_hash_07, second_hash_09);
if(first_hash_07 == second_hash_07 &&
first_hash_09 == second_hash_09)
positions.push_back(int(i - a.size() + 1));
}
fout << positions.size() << "\n";
if(positions.size() > 1000)
size = 1000;
else
size = positions.size();
for (int i = 0; i < size; i++)
fout << positions[i] << " ";
return 0;
}