Xin chào mọi người, em đang học đến Hash-table, cụ thể là đang học đến giải thuật Rabin-Karp, và nó khá khó, em đã hiểu được ý tưởng bài toán, và giải thuật hoạt động thế nào. Song khi thực hiện giải thuật thì gặp kết quả sai.
Cụ thể, đề bài là, trả về vị trí của chuỗi con trong chuỗi.
Ví dụ:
aba
abacaba
Output: 0 4.
Ví dụ này thì thuật toán chạy đúng kết quả.
Ví dụ 2:
Test
testTesttesT
Output: 4
Kết quả: pHash(Test) :118188920
H[4] (Test) : 957396881
Lúc này khi tính hàm preComputeHashes thì nó ra sai kết quả. Em đang phân vân không biết hàm polyHash tính sai hay là hàm preComputeHashes tính sai nữa. Mọi người xem và góp ý giúp em với. Em xin cảm ơn nhiều.
// Assignment3Problem3.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
// Assignment3Problem3.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include "pch.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
struct Data {
string pattern, text;
};
Data read_input() {
Data data;
cin >> data.pattern >> data.text;
return data;
}
void print_occurrences(const vector<int>& output) {
for (size_t i = 0; i < output.size(); ++i)
cout << output[i] << " ";
cout << "\n";
}
long long polyHash(string &p, int prime, int x)
{
long long hash = 0;
for (int i = p.length() - 1; i >= 0; i--)
{
hash = ((hash*x + p[i])%prime+prime)%prime;
}
return hash;
}
vector<long long> preComputeHashes(string t, int pLength, int prime, int x)
{
vector<long long> H(t.length() - pLength + 1);
string s = t.substr(t.length() - pLength, t.length() - 1);
H[H.size() - 1] = polyHash(s, prime, x);
int y = 1;
for (int i = 1; i <= pLength; i++)
y = ((y*x) % prime + prime) % prime;
for (int i = t.length() - pLength - 1; i >= 0; i--)
H[i] = ((x*H[i + 1] + t[i] - y * t[i + pLength]) % prime + prime) % prime;
return H;
}
vector<int> get_occurrences(const Data& input) {
string p = input.pattern, t = input.text;
vector<int> result;
int prime = 1000000007, x = 1;
long long pHash = polyHash(p, prime, x);
vector<long long> H = preComputeHashes(t, p.length(), prime, x);
for (size_t i = 0; i <= t.length() - p.length(); i++)
{
if (pHash != H[i])
continue;
bool isSame = true;
for (int j = i; j < i + p.length(); j++)
{
if (t[j] != p[j - i])
{
isSame = false;
break;
}
}
if (isSame == true)
result.push_back(i);
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
print_occurrences(get_occurrences(read_input()));
return 0;
}
hay 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?