Knyffen
b9645f15ff
The text and pattern are now streamed directly (skipping saving them to strings). Knowing exactly what string was matched has now been delegated to the Rabin_fingerprint_process.
56 lines
1.5 KiB
C++
56 lines
1.5 KiB
C++
/* #define NDEBUG */
|
|
/* #include "Rabin_fingerprint.hpp" */
|
|
#include "general_library.hpp"
|
|
#include "processes.hpp"
|
|
|
|
#include <iostream>
|
|
#include <stdint.h>
|
|
#include <math.h>
|
|
#include <string>
|
|
#include <fstream>
|
|
|
|
int main() {
|
|
/* std::ifstream T("books/the_complete_works_of_william_shakespeare.txt"); */
|
|
std::ifstream T("books/genji_monogatari_english.txt");
|
|
std::ifstream P("books/pattern.txt");
|
|
|
|
char c;
|
|
size_t P_length = 0;
|
|
std::cout << "Searching for pattern:" << std::endl;
|
|
std::cout << " ";
|
|
while(P.get(c)) {
|
|
std::cout << c;
|
|
P_length++;
|
|
|
|
}
|
|
std::cout << std::endl << std::endl;
|
|
|
|
P.clear(); // clear fail and eof bits
|
|
P.seekg(0, std::ios::beg); // back to the start!
|
|
|
|
uint32_t irreducible_polynomial = get_random_irreducible_polynomial_in_Z2(31);
|
|
size_t window_size_in_bits = P_length*8;
|
|
|
|
// Hash the pattern
|
|
Rabin_fingerprint_process phiP(irreducible_polynomial, (size_t)window_size_in_bits);
|
|
while(P.get(c)) {
|
|
phiP.stream_char(c);
|
|
}
|
|
|
|
// Hash the text
|
|
Rabin_fingerprint_process phiT(irreducible_polynomial, window_size_in_bits);
|
|
size_t index = 0;
|
|
while(T.get(c)) {
|
|
phiT.stream_char(c);
|
|
index++;
|
|
if (phiT.get_fingerprint() == phiP.get_fingerprint())
|
|
std::cout << "Match found at index " << index-P_length << " with the text \"" << phiT.get_string_in_window() << "\"" << std::endl;
|
|
}
|
|
|
|
std::cout << std::endl;
|
|
std::cout << "Done!" << std::endl;
|
|
|
|
return EXIT_SUCCESS;
|
|
}
|
|
|