algorytmy wyszukiwania tekstu

[morarz]

Jak można ten kod poniżej 'algorytm' przerobić aby działał w Builderze? , dodałem biblioteke

Kod: Zaznacz cały

#include<string>

, poniewaz działamy na stringach ale podczas uruchamiania wyskakuje mi bład?? Chciałbym aby ten algorytm wyszukał mi tekst w ListBox.
Mając na przykład Algorytm naiwny napisany w Dev C++ :

Kod: Zaznacz cały

int Naiwny(string tekst, string wzorzec)
{int i,j;
int m = wzorzec.size();
int n = tekst.size();

i=0; 
  while(i<=n-m)
{
     j=0;
     while((j<m)&&(wzorzec[j]==tekst[i+j])) j++;
     if (j==m) cout<<"tutaj "<<i+1<<"\n";
     i++;         
}
return (i+1);
}
int main()
{
string wzorzec;
string
tekst;
cout<<"podaj tekst\n";cin>>tekst;
    cout<<"Podaj wzorzec\n ";cin>>wzorzec;
    cout<<"Indeksy wystapien wzorca w tekscie\n";
    Naiwny (tekst, wzorzec);
system ("pause");
}

[Cyfrowy Baron]

Wymagane obiekty:

Button1 - do uruchomienia zdarzenia wyszukiwania
Edit1 - do wpisywania tekstu wyszukiwanego
ListBox1 - zawiera listę w której będzie się odbywać wyszukiwanie

Kod: Zaznacz cały

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
static int x = -1;
Lab_1:
for(int i = x + 1; i < ListBox1->Items->Count; i++)
{
  String tekst = ListBox1->Items->Strings[i].LowerCase();
  String find = Edit1->Text.LowerCase();
  int y = tekst.Pos(find);
  if(y > 0)
  {
   ListBox1->Perform(LB_SELECTSTRING, x,(LPARAM)tekst.c_str());
   x = ListBox1->Perform(LB_FINDSTRINGEXACT, x,(LPARAM)tekst.c_str());
   ListBox1->SetFocus();
   return;
  }
}

int idx = MessageBox(Handle, "Zakończono przeszukiwanie! Nic więcej "
"nie odnaleziono.\nCzy chcesz rozpocząć przeszukiwanie od początku?",
"Wyszukiwanie zakończone", MB_YESNO | MB_ICONINFORMATION | MB_DEFBUTTON2 | MB_APPLMODAL);
x = -1;
if(idx == ID_YES)
{
  goto Lab_1;
}
}
//---------------------------------------------------------------------------


Przedstawiłem wyszukiwanie kontekstowe. Wyszukiwanie elementów listy znajdziesz tutaj:

► patrz serwis: Cyfrowy Baron dział: porady ListBox Wyszukiwanie elementu listy poprzez podanie jego nazwy.

Jeżeli będziesz potrzebował wyszukiwania tekstu w obiektach typu TMemo lub TRichEdit to polecam:

► patrz serwis: Cyfrowy Baron dział: porady TRichEdit & Memo Wyszukiwanie tekstu w RichEdit.

[polymorphism]

Z tym goto to lekka przesada, pętle są od tego:

Kod: Zaznacz cały

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   int x = 0;

   while(1)
   {
      for(int i = x; i < ListBox1->Items->Count; i++)
      {
         String tekst = ListBox1->Items->Strings[i].LowerCase();
         String find = Edit1->Text.LowerCase();
         
         int y = tekst.Pos(find);
         
         if(y > 0)
         {
            ListBox1->Perform(LB_SELECTSTRING, x,(LPARAM)tekst.c_str());
            x = ListBox1->Perform(LB_FINDSTRINGEXACT, x,(LPARAM)tekst.c_str());
            ListBox1->SetFocus();
            return;
         }
      }

      if(MessageBox(Handle,
               "Zakończono przeszukiwanie! Nic więcej "
               "nie odnaleziono.\nCzy chcesz rozpocząć przeszukiwanie od początku?",
               "Wyszukiwanie zakończone",
               MB_YESNO | MB_ICONINFORMATION | MB_DEFBUTTON2 | MB_APPLMODAL) == ID_NO)break;
      x = 0;
   }
}


[morarz]

Przedstawiłem wyszukiwanie kontekstowe. Wyszukiwanie elementów listy znajdziesz tutaj:
ListBox Wyszukiwanie elementu listy poprzez podanie jego nazwy.

to już widziałem...ale własnie chodziło mi o taki algorytm. Dzięki
Ty chyba znasz odpowiedz na wszystkie pytania co nie ?

Poniżej aplikacja wyszukująca tekst w ListBox wraz z algorytmem wyszukiwania Cyfrowego Barona ,moze komuś się przyda(z optymalizowanym kodem )...

[Cyfrowy Baron]

Z tym goto to lekka przesada, pętle są od tego:

Twój kod niestety się nie sprawdza, zatrzymuje się na pierwszym napotkanym elemencie i zaprzestaje przeszukiwania. Powinno być:

Kod: Zaznacz cały

//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
static int x = -1;

   while(1)
   {
      for(int i = x + 1; i < ListBox1->Items->Count; i++)
      {
         String tekst = ListBox1->Items->Strings[i].LowerCase();
         String find = Edit1->Text.LowerCase();
         
         int y = tekst.Pos(find);
         
         if(y > 0)
         {
            ListBox1->Perform(LB_SELECTSTRING, x,(LPARAM)tekst.c_str());
            x = ListBox1->Perform(LB_FINDSTRINGEXACT, x,(LPARAM)tekst.c_str());
            ListBox1->SetFocus();
            return;
         }
      }

      if(MessageBox(Handle,
               "Zakończono przeszukiwanie! Nic więcej "
               "nie odnaleziono.\nCzy chcesz rozpocząć przeszukiwanie od początku?",
               "Wyszukiwanie zakończone",
               MB_YESNO | MB_ICONINFORMATION | MB_DEFBUTTON2 | MB_APPLMODAL) == ID_NO)break;
      x = -1;
   }   
}
//---------------------------------------------------------------------------


pętle są od tego:

ja wolę funkcję goto.

[polymorphism]

Twój kod niestety się nie sprawdza,

Fakt, nie zauważyłem Perform z LB_FINDSTRINGEXACT. Głównie chodziło o użycie pętli while zamiast goto.

ja wolę funkcję goto.

Bo?

[Cyfrowy Baron]

Bo?

Bo tak i już! Co to za pytanie?! Jedni wolą kolor zielony, a ja wolę błękitny, ale o gustach się nie dyskutuje.
Jak widzę masz tendencję do mieszania i doszukiwania się dziur tam gdzie ich nie ma. Tak z ciekawości: jesteś zwolennikiem PIS'u?

[Witold]

Kod: Zaznacz cały

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
static int x = -1;
Lab_1:
for(int i = x + 1; i < ListBox1->Items->Count; i++)
{
  String tekst = ListBox1->Items->Strings[i].LowerCase();
  String find = Edit1->Text.LowerCase();
  int y = tekst.Pos(find);
  if(y > 0)
  {
   ListBox1->Perform(LB_SELECTSTRING, x,(LPARAM)tekst.c_str());
   x = ListBox1->Perform(LB_FINDSTRINGEXACT, x,(LPARAM)tekst.c_str());
   ListBox1->SetFocus();
   return;
  }
}

Tak się zastanawiam czy tu wyszukiwanie nie jest robione trzy razy zamiast jednego.
Raz w pętli, potem przez LB_SELECTSTRING i na koniec przez LB_FINDSTRINGEXACT.
No i zmienna find jest tworzona/kasowana przy każdej iteracji pętli mimo że się nie zmienia.

[Cyfrowy Baron]

No i zmienna find jest tworzona/kasowana przy każdej iteracji pętli mimo że się nie zmienia.

Fakt! Można ją zdefiniować przed pętlą, tak będzie nawet lepiej.

Raz w pętli, potem przez LB_SELECTSTRING i na koniec przez LB_FINDSTRINGEXACT.

Komunikat LB_SELECTSTRING wyszukuje i zaznacza element na liście. Komunikat LB_FINDSTRINGEXACT również, ale go nie zaznacza i rzeczywiście można się jednego pozbyć, czyli tego drugiego.

Poradę pisałem szybko i nie zastanawiałem się nad nią dłużej.
Zamieszczam zoptymalizowany kod.

Kod: Zaznacz cały

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
static int x = -1;
String find = Edit1->Text.LowerCase();

Lab_1:
for(int i = x + 1; i < ListBox1->Items->Count; i++)
{
  String tekst = ListBox1->Items->Strings[i].LowerCase();

  int y = tekst.Pos(find);
  if(y > 0)
  {
   x = ListBox1->Perform(LB_SELECTSTRING, x,(LPARAM)tekst.c_str());
   ListBox1->SetFocus();
   return;
  }
}

int idx = MessageBox(Handle, "Zakończono przeszukiwanie! Nic więcej "
"nie odnaleziono.\nCzy chcesz rozpocząć przeszukiwanie od początku?",
"Wyszukiwanie zakończone", MB_YESNO | MB_ICONINFORMATION | MB_DEFBUTTON2 | MB_APPLMODAL);
x = -1;
if(idx == ID_YES)
{
  goto Lab_1;
}

}
//---------------------------------------------------------------------------


[Witold]

Zamieszczam zoptymalizowany kod.

No nie wiem, załóżmy że na pozycji 961 w ListBox’e znajduje się szukany element, wtedy wywołujesz:

Kod: Zaznacz cały

ListBox1->Perform(LB_SELECTSTRING, x,(LPARAM)tekst.c_str());


co skutkuje ponownym "wewnętrznym" przeszukaniem ListBox’a aby zaznaczyć dany element. Można by użyć: ListBox1->ItemIndex = x = i;

Jeszcze tak sobie myślę, że trzymanie pozycji od której trzeba szukać, w lokalnej zmiennej x z modyfikatorem static spowoduje problemy , gdy x będzie inny niż -1 (przeszukiwanie od początku) , i zmieni się słowo szukane lub elementy listy.

[Cyfrowy Baron]

Z funkcji Perform można zrezygnować. Poruszam się utartymi ścieżkami, ale zawsze i tak poświęcam czas na optymalizację.
Oto poprawiony kod:

Kod: Zaznacz cały

static int x = -1;
String find = Edit1->Text.LowerCase();

Lab_1:
for(int i = x + 1; i < ListBox1->Items->Count; i++)
{
  String tekst = ListBox1->Items->Strings[i].LowerCase();

  int y = tekst.Pos(find);
  if(y > 0)
  {
   x = i;
   ListBox1->ItemIndex = i;
   ListBox1->SetFocus();
   return;
  }
}

int idx = MessageBox(Handle, "Zakończono przeszukiwanie! Nic więcej "
"nie odnaleziono.\nCzy chcesz rozpocząć przeszukiwanie od początku?",
"Wyszukiwanie zakończone", MB_YESNO | MB_ICONINFORMATION | MB_DEFBUTTON2);
x = -1;
if(idx == ID_YES)
{
  goto Lab_1;
}


Jeszcze tak sobie myślę, że trzymanie pozycji od której trzeba szukać, w lokalnej zmiennej x z modyfikatorem static spowoduje problemy , gdy x będzie inny niż -1 (przeszukiwanie od początku) , i zmieni się słowo szukane lub elementy listy.

Przyjrzyj się dokładniej konstrukcji kodu, a zauważysz że ta zmienna może przyjąć tylko wartości z zakresu od -1 do ListBox1->Items->Count - 1; więc ta zmienna nie stanowi żadnego problemu, gdyż w żaden sposób nie może wyjść poza zadany zakres, gdyż jeżeli na liście zostanie odnalezione poszukiwane słowo to zmienna x przyjmie wartość tego indeksu, jeżeli słowo nie zostanie odnaleziony wyskoczy komunikat z pytaniem o wyszukiwanie od początku, przy TAK funkcja goto zawsze odsyła do początku wyszukiwania, co może za każdym razem skutkować wyszukiwaniem brakującego wyrazu. Bez komunikatu program tutaj by się zapętlił, jednak zabezpiecza przed tym komunikat. Przy NIE zmienna x zatrzyma swoją wartość równą -1. Prześledź kod krok po kroku i wskaż sytuację w której ten kod się "wysypie". Ja nie widzę sytuacji w której zmienna x mogłaby wyjść poza zadany zakres.

[Witold]

Ja nie widzę sytuacji w której zmienna x mogłaby wyjść poza zadany zakres.

Ja nie napisałem że zmienna x może wyjść poza zakres. Załóżmy że w ListBox’ie są słowa:

absolutely
accept
accident
achieve
ability
able
about
…

Szukam słowa: achieve zmienna x będzie równa 3, potem chcę znaleźć wyraz accept (index 1) dostanę komunikat że "…nie odnaleziono…", a przecież jest on w ListBox’ie. Wydaję mi się, że gdy zmienia się szukany wyraz (lub zawartość ListBox’a), zmienna x powinna być tak ustawiona aby przeszukiwać od początku (-1).

[Cyfrowy Baron]

Rzeczywiście! To mi umknęło, ale poradzę sobie z tym z wykorzystaniem kolejnej zmiennej statycznej:

Kod: Zaznacz cały

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
static int x = 0;
String find = Edit1->Text.LowerCase();
static String tmp = "";


Lab_1:
for(int i = x; i < ListBox1->Items->Count; i++)
{
  String tekst = ListBox1->Items->Strings[i].LowerCase();

  int y = tekst.Pos(find);
  if(y > 0)
  {
   x = i + 1;
   tmp = find;
   ListBox1->ItemIndex = i;
   ListBox1->SetFocus();
   return;
  }
}
int idx;
if(tmp == find)
idx = MessageBox(Handle, "Zakończono przeszukiwanie! Nic więcej "
"nie odnaleziono.\nCzy chcesz rozpocząć przeszukiwanie od początku?",
"Wyszukiwanie zakończone", MB_YESNO | MB_ICONINFORMATION | MB_DEFBUTTON2);
x = 0;
if(idx == ID_YES || tmp != find)
{
  goto Lab_1;
}
}
//---------------------------------------------------------------------------


Myślałem o wykorzystaniu rekurencji zamiast funkcji goto, lecz nic z tego nie wychodzi, jak jedno działa to drugie już nie, a kod staje się coraz bardziej skomplikowany.