Witam mam napisac program porównujący wyszukiwanie wzorca algorytmem naiwnym i Rabina Karpa z tym że ALGORYTM RABINA KARPA MUSZE UOGOLNIC NA WZORCE DWUWYMIAROWE.TZN Szukajac w tablicy wzorca np
17
95 traktujemy go jako płaski i nastepnie zapisujemy wierszami tj 1795
nastepnie przesuwamy w dół obcinamy pierwszy wiersz i dodajemy ostatni przesuniecie w prawo:obcinamy kolumne z lewej i dodajemy z prawej-jesli chodzio te przesuniecia nie jestem do koncapewien czy to tak jest na pewno ogolnie chodzi o UOGOLNIENIE ALG rABINA-KARPA NA WZORCE DWUWYMIAROWE moze mi ktos pomóc bo nie wiem jak to zrobic wC++
oto moj kod z normalnym wyszukiwaniem RK i alg naiwnym (moze to jest to o co chodzi-do konca nie czaje tego uogulnienia)Dzieki z góry za jakąś pomoc
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define position vector<int>
extern __inline__ unsigned long long int czas();
position simple_szukaj(const char* szukaj_text, ifstream& plik, int rozmiarpliku);
position kmp(const char* szukaj_text, ifstream& plik, int rozmiarpliku);
position rk(const char* szukaj_text, ifstream& plik, int rozmiarpliku);
typedef position (*VPF)(const char* szukaj_text, ifstream& plik, int rozmiarpliku);
void szukaj(VPF fun, const char* szukaj_text, ifstream& plik);
// Funkcja czasowa
extern __inline__ unsigned long long int czas() {
unsigned long long int ilosc;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (ilosc));
return ilosc;
}
// Wyszukiwanie RK
position rk(const char* szukaj_text, ifstream& plik, int rozmiarpliku) {
position pos;
int textLenght = strlen(szukaj_text);
// powrót na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
// Algorytm RK
int h = 1;
int p = 0;
int t = 0;
const int first = 127;
const int modulo = 10;
char znak;
char znak_temp;
for (int i = 1; i < textLenght; i++)
h = (h * modulo);
// powrót na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
for (int i = 0; i < textLenght; i++) {
plik.get(znak);
t = (modulo * t + znak);
p = (modulo * p + szukaj_text[i]);
}
// powrot na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
for (int i = 0; i < rozmiarpliku - textLenght; i++) {
if (p == t) {
int j = 0;
for (j = 0; j < textLenght; j++) {
plik.seekg(i + j, ios::beg);
plik.get(znak);
if (szukaj_text[j] != znak)
break;
}
if (j == textLenght)
pos.push_back(i);
}
plik.seekg(i, ios::beg);
plik.get(znak);
plik.seekg(i + textLenght, ios::beg);
plik.get(znak_temp);
t = (modulo * (t - znak * h) + znak_temp);
}
// powrot na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
return pos;
}
// Wyszukiwanie najwne
position simple_szukaj(const char* szukaj_text, ifstream& plik, int rozmiarpliku) {
int textLenght = strlen(szukaj_text);
char *buffer = 0;
position pos;
// Powrót na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
// Czytanie znak po znaku w poszukiwaniu frazy
char charTemp = ' ';
int subPosition = 0;
while (true) {
plik.seekg(subPosition, ios::beg);
if (!plik.get(charTemp))
break;
// Brak zgody pierwszej litery frazy z przeczytanym znakiem
if (charTemp != szukaj_text[0]) {
subPosition++;
continue;
}
// czytanie pliku-dalsze porównanie
buffer = new char[textLenght + 1];
for (int i = 0; i <= textLenght; i++)
buffer[i] = 0;
plik.seekg(subPosition, ios::beg);
plik.read(buffer, textLenght);
if (strcmp(buffer, szukaj_text) == 0)
pos.push_back(subPosition);
delete [] buffer;
subPosition++;
}
// Powrót na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
return pos;
}
// Wyszukiwanie KMP
position kmp(const char* szukaj_text, ifstream& plik, int rozmiarpliku) {
position pos;
int textLenght = strlen(szukaj_text);
// Obliczenie tablicy prefikso-sufiksowych
int *pre = new int[textLenght + 1];
for (int i = 0; i < textLenght + 1; i++)
pre[i] = 0;
if (textLenght > 2) {
int t = 0;
for (int j = 2; j <= textLenght; j++) {
while ((t > 0) && (szukaj_text[t] != szukaj_text[j - 1]))
t = pre[t];
if (szukaj_text[t] == szukaj_text[j-1])
t++;
pre[j] = t;
}
}
// powrót na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
// Algorytm KMP
int i = 1;
int j = 0;
char znak;
while (i <= rozmiarpliku - textLenght + 1) {
j = pre[j];
plik.seekg(i + j - 1, ios::beg);
plik.get(znak);
while((j < textLenght) && (szukaj_text[j] == znak)) {
j++;
plik.seekg(i + j - 1, ios::beg);
plik.get(znak);
}
if (j == textLenght)
pos.push_back(i - 1);
i += (1 > (j - pre[j])) ? 1 : (j - pre[j]);
}
delete [] pre;
// powrot na poczatek pliku
plik.clear();
plik.seekg(0, ios::beg);
return pos;
}
void szukaj(VPF fun, const char* szukaj_text, ifstream& plik, int rozmiarpliku) {
position temp;
unsigned long long int start = czas();
temp = fun(szukaj_text, plik, rozmiarpliku);
unsigned long long int stop = czas();
cout << "Wyszukane pozycje w pliku: ";
for (int i = 0; i < temp.size(); i++)
cout << temp[i] << " ";
cout << endl;
cout << "Wykonano w: " << stop - start << endl;
}
int main(int argc, char *argv[]) {
ifstream plik;
plik.open("tablica.txt", ifstream::binary);
int rozmiarpliku = 0;
char charTemp;
while(plik.get(charTemp))
rozmiarpliku++;
char text[256];
cout << "Podaj text do wyszukania: ";
cin.getline(text, 255);
cout << endl << "Wyszukanie rabina-karpa" << endl;
szukaj(rk, text, plik, rozmiarpliku);
cout << endl << "Wyszukanie najwne" << endl;
szukaj(simple_szukaj, text, plik, rozmiarpliku);
cout << endl << "Wyszukanie kmp" << endl;
szukaj(kmp, text, plik, rozmiarpliku);
plik.close();
system("PAUSE");
return EXIT_SUCCESS;
}