Witam.
Otóż, muszę napisać program, przeszukujący tekst w poszukiwaniu słowo klucza algorytmem. Samowyszukiwanie tym algorytmem posiadam i działa ono bardzo dobrze, jednak musiałem przebudować całą funkcję main() i program ten nie do końca chodzi tak jak należy. Wielokrotnie debugowałem program i poprawiałem kod optymalizując go, jednak jak działał wtedy tak działa dalej.
Oto kod
#include<iostream>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<ctime>
using namespace std;
void liczKMP(char *wzorzec, int *KMP, int dlugoscwz)
{
KMP[1] = 0;
int i = 0 ;
for (int j = 1; j<dlugoscwz; j++)
{ //obliczam kmp[j+1]
while (i>0 && wzorzec[j+1]!=wzorzec[i+1])
{
i = KMP[i];
}
if (wzorzec[j+1] == wzorzec[i+1]) i++;
KMP[j+1] = i;
}
}
void wypisz(int numer, char *wzorzec)
{//wypisuje pozycje na ktorej byl wzorzec i wzorzec
cout<<wzorzec <<" " <<numer <<endl;
}
void funkcjaKMP(char* wzorzec, string* tekst2, int *KMP, int dlugoscwz, int dlugosc)
{
string h=*tekst2;
char *tekst;
tekst=new char[h.length()];
for(int a=0;a<h.length();a++)
{
tekst[a]=tekst[a]+(char)h[a];
}
//cout<<h;
liczKMP(wzorzec, KMP, dlugoscwz);
//cout << "W funkcji funkcjaKMP()"<<endl;
int j = 0;
for (int i = 1; i<=dlugosc; i++)
{
while ((j>0)&& (wzorzec[j+1]!= tekst[i]))
{
j = KMP[j];
}
if (tekst[i]==wzorzec[j+1]) j++;
if (j==dlugoscwz)
{
wypisz(i-j+1, wzorzec);
j = KMP[j]; //szukamy dalej
}
}
}
//Funkcja main
//-----------------------------------------
int main()
{
//ilosc slow do wczytania
int *n;
n=new int;
//wzorce
char **wzorzec;
//tekst
vector<string> tekst;
//inne potrzebne
string napis, tekst2;
int k=21;
cin>>*n;
if(k<*n)
{k=*n;}
wzorzec=new char*[*n];
for(int x=0;x<k;x++)
{
wzorzec[x]=new char[k];
}
for(int v=0;v<*n;++v)
{
for(int x=0;x<k;++x)
{
wzorzec[v][x]=' ';
}
}
for(int a=0;a<*n;a++)
{
scanf("%s", wzorzec[a]);
}
//wypisywanie wzorcow
for(int y=0;y<*n;y++)
{
cout<<y <<" - ";
for(int z=0;z<20;++z)
{cout<<wzorzec[y][z];}
cout<<endl;
}
//wczytywanie tekstu
cin.clear();
while(cin>>tekst2)
{
tekst2=tekst2+" ";
tekst.push_back(tekst2);
if(*tekst2.c_str()==EOF)
break;
cin.clear();
}
for(int x=0;x<tekst.size();x++)
cout<<tekst[x];
int *KMP;
for(int a=0;a<*n;a++)
{
KMP=new int[strlen(wzorzec[a])+1];
funkcjaKMP(wzorzec[a],&tekst.front(),KMP,strlen(wzorzec[a]), tekst.size());
delete[] KMP;
}
//czyszczenie
if(*n<20)
*n=k;
for(int x=0;x<*n;x++)
{
delete wzorzec[x];
}
delete[] wzorzec;
delete n;
return 0;
Zaznaczam, że wpisywałem tekst parokrotnie ręcznie ale najczęściej zwyczajnie przekierowuje standardowe wejście na jeden z plików, w jakich ma być zrobione wyszukiwanie. Plik załączam również.
Wspomnę, że kod kompiluje się dobrze i częściowe wyszukiwanie zostaje spełnione jednak nie do końca.
Edytka
Poprawiłem większość błędów jednak jest problem w kodzie. Chodzi chyba o moje magiczne przejście w funkcjaKMP z string* na char*.
- dane.txt (5 KB) - ściągnięć: 192
