Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> [php] szukanie frazy w frazie
hhg
post
Post #1





Grupa: Zarejestrowani
Postów: 316
Pomógł: 0
Dołączył: 5.07.2006

Ostrzeżenie: (0%)
-----


prosze nie pytajcie dlaczego nie korzystam ze strstr(), nie ja to wymyslalem biggrin.gif

Mam napisac program ktory szuka jednej frazy ($search) w innej frazie ($belt). Ma szukac w nastepujacy sposob: przechodzi po znakach z $belt, jezeli dany znak z $belt pokrywa sie ze pierwszym z $search to przechodzi ze stanu 0 w stan 1 i sprawdza kolejny. Jezeli sie zgadza to przechodzi w stan 2 itd. Logicznym jest ze jezeli nr stanu jest rowny dlugosci $search to napis zostal znaleziony. Jest jeszcze znak * wystepujacy w $search ktory zastepuje kazdy inny, czyli w jego wypadku automatycznie przechodzimy w stan wyższy.

Mam jednak powien problem bo moj program dziala nie dla wszystkich przypadków.

Oto kod:

  1. <?php
  2.  
  3. function stringtoarray($string){
  4. $len = strlen($string);
  5.  
  6. $cur = 0;
  7.  
  8. $characterarray = array();
  9.  
  10. while($cur < $len){
  11. $char = $string{$cur};
  12. array_push($characterarray,$char);
  13. $cur = $cur + 1;
  14. }
  15.  
  16. return $characterarray;
  17. }
  18.  
  19.  
  20. $belt = stringtoarray('ala ma kota');
  21. $search = stringtoarray('m*');
  22. $table = array();
  23.  
  24. for ($j=0; $j<count($search); $j++)
  25. for ($i=0; $i<count($belt); $i++)
  26. $table[$j][$i] = 0;
  27.  
  28. $j = 0;
  29.  
  30. for ($i=0; $i<count($belt); $i++) {
  31.  
  32. echo '- porownanie belt[' . $i . '] = ' . $belt[$i] . ', search[' . $j . '] = ' . $search[$j];
  33.  
  34. if ($belt[$i] == $search[$j] || $search[$j] == '*') {
  35. $j++;
  36. } else {
  37. if ($j) $j--;
  38. }
  39.  
  40.  
  41. echo ' stan ' . $j . '<br />';
  42. $table[$j-1][$i] = $j;
  43.  
  44. if ($j == count($search)) {
  45. echo 'znaleziono napis!<br />';
  46. $j = 0;
  47. }
  48.  
  49. if ($j) echo '<br />';
  50. }
  51.  
  52.  
  53. echo '<br /><br />tablica przejsc: <br />nr poszczegolnych znakow / stany';
  54. for ($j=0; $j<count($search); $j++) {
  55. echo '<div style="float:left;"><pre>';
  56. var_dump($table[$j]);
  57. echo '</pre></div>';
  58. }
  59.  
  60. ?>


teraz pięknie znajdzie 'm*' jako 'ma'

na samym dole wygeneruje tablice przejsc, ale nas to nie obchodzi.

Niestety nie działa to dla przypadku np.

$belt = 'alaalaalaalab';
i
$search = 'alab';

dlaczego? jak to poprawić? sa jakies inne dla ktorych nie zadziała?

prosze o pomoc
Go to the top of the page
+Quote Post
 
Start new topic
Odpowiedzi (1 - 8)
Darti
post
Post #2





Grupa: Zarejestrowani
Postów: 1 076
Pomógł: 62
Dołączył: 6.03.2005
Skąd: Wroc

Ostrzeżenie: (0%)
-----


  1. <?php
  2.  
  3. function stringtoarray($string){
  4. $len = strlen($string);
  5.  
  6. $cur = 0;
  7.  
  8. $characterarray = array();
  9.  
  10. while($cur < $len){
  11. $char = $string{$cur};
  12. array_push($characterarray,$char);
  13. $cur = $cur + 1;
  14. }
  15.  
  16. return $characterarray;
  17. }
  18.  
  19.  
  20. $belt = stringtoarray('ala ma kota');
  21. $search = stringtoarray('m*');
  22. $table = array();
  23.  
  24. for ($j=0; $j<count($search); $j++)
  25. for ($i=0; $i<count($belt); $i++)
  26. $table[$j][$i] = 0;
  27.  
  28. $j = 0;
  29.  
  30. for ($i=0; $i<count($belt); $i++) {
  31.  
  32. echo '- porownanie belt[' . $i . '] = ' . $belt[$i] . ', search[' . $j . '] = ' . $search[$j];
  33.  
  34. if ($belt[$i] == $search[$j] || $search[$j] == '*') {
  35. $j++;
  36. } else {
  37. if ($j) {
  38. $j--;
  39. $i--;  //tutaj
  40. }
  41. }
  42.  
  43.  
  44. echo ' stan ' . $j . '<br />';
  45. $table[$j-1][$i] = $j;
  46.  
  47. if ($j == count($search)) {
  48. echo 'znaleziono napis!<br />';
  49. $j = 0;
  50. }
  51.  
  52. if ($j) echo '<br />';
  53. }
  54.  
  55.  
  56. echo '<br /><br />tablica przejsc: <br />nr poszczegolnych znakow / stany';
  57. for ($j=0; $j<count($search); $j++) {
  58. echo '<div style="float:left;"><pre>';
  59. var_dump($table[$j]);
  60. echo '</pre></div>';
  61. }
  62.  
  63. ?>


Ten post edytował Darti 14.11.2007, 03:15:13


--------------------
The answer is out there, Neo. It's looking for you. And it will find you, if you want it to.
SERVER_SOFTWARE : Apache/2.2.4 (Win32) PHP/5.2.1
MySQL Client API version : 5.0.27
Go to the top of the page
+Quote Post
nevt
post
Post #3





Grupa: Przyjaciele php.pl
Postów: 1 595
Pomógł: 282
Dołączył: 24.09.2007
Skąd: Reda, Pomorskie.

Ostrzeżenie: (0%)
-----


macie koledzy skłonność do komplikowania prostych rzeczy...
  1. <?php
  2. function str_find($search, $belt)
  3. {
  4. $offset = 0;
  5. $success = strlen($search);
  6. $stop = strlen($belt);
  7. for($i=0; $i < $stop; $i++)
  8. if(($search{$offset} == $belt{$i}) or ($search{$offset} == '*'))
  9. if(++$offset == $success)
  10. return $i; //znaleziono, zwraca nr znaku w $belt gdzie zaczyna się $search
  11. else;
  12. else
  13. {
  14. $i -= $offset; //wystarczy ta zamiana !!
  15. $offset = 0;
  16. }
  17. return -1; // nie znaleziono
  18. }
  19.  
  20. if(str_find('a*a', 'kubala') >= 0)
  21. echo 'Znaleziono!';
  22. else
  23. echo 'Nie znaleziono!';
  24. ?>


Powodzenia na zaliczeniu...

Ten post edytował nevt 14.11.2007, 10:36:07


--------------------

-
Oh no, my young coder. You will find that it is you who are mistaken, about a great many things... -
Go to the top of the page
+Quote Post
heaven
post
Post #4





Grupa: Nieautoryzowani
Postów: 92
Pomógł: 15
Dołączył: 21.10.2006

Ostrzeżenie: (0%)
-----


Twoja procedura nie dziala
  1. <?php
  2. if(str_find('lla', 'kuballla') >= 0)
  3. echo 'Znaleziono!';
  4. else
  5. echo 'Nie znaleziono!'
  6. ?>

Nie znaleziono tongue.gif

Tu jest poprawny kod.
  1. <?php
  2. function str_find($search, $belt)
  3. {
  4. for($i=0; $i<strlen($belt)-strlen($search)+1;$i++)
  5. for($j=0; $j<strlen($search); $j++)
  6. if(($belt{$i+$j} == $search{$j}) || ($search{$j} == '*'))
  7.  if ($j == strlen($search)-1) return $i;
  8.  else continue;
  9. else break;
  10. return -1;
  11. }
  12. ?>


Ten post edytował heaven 14.11.2007, 09:07:42
Go to the top of the page
+Quote Post
nevt
post
Post #5





Grupa: Przyjaciele php.pl
Postów: 1 595
Pomógł: 282
Dołączył: 24.09.2007
Skąd: Reda, Pomorskie.

Ostrzeżenie: (0%)
-----


nadal komplikujecie sobie życie... faktycznie przeoczyłem ten przypadek, ale do korekty wystarczy dodać 1 podstawienie a nie dodatkową pętlę... poprawka naniesiona w poprzednim poście. bawcie się dobrze.


--------------------

-
Oh no, my young coder. You will find that it is you who are mistaken, about a great many things... -
Go to the top of the page
+Quote Post
heaven
post
Post #6





Grupa: Nieautoryzowani
Postów: 92
Pomógł: 15
Dołączył: 21.10.2006

Ostrzeżenie: (0%)
-----


No zwal jak zwal...
Moj i Twoj kod przechodzi taka sama ilosc razy po stringach (jednak twoj robi w niektorych przypadkach wiecej niepotrzebnych przejsc) wiec nie nazwalbym tego komplikowaniem tym bardziej ze moj kod jest bardziej intuicyjny
No ale racja jest jak ... kazdy ma swoja

Ten post edytował heaven 14.11.2007, 12:30:20
Go to the top of the page
+Quote Post
hhg
post
Post #7





Grupa: Zarejestrowani
Postów: 316
Pomógł: 0
Dołączył: 5.07.2006

Ostrzeżenie: (0%)
-----


da sie jeszcze ten kod jakkolwiek (doslownie jakkolwiek ) zoptymalizowac?
  1. <?php
  2.  
  3. function str_find($search, $belt) {
  4.  
  5. $offset = 0;
  6. $success = strlen($search);
  7. $stop = strlen($belt);
  8. $remember = null;
  9.  
  10.  
  11.  
  12. for($i=0; $i < $stop; $i++)
  13. if(($search{$offset} == $belt{$i}) or ($search{$offset} == '*')) {
  14.  
  15.  
  16.  
  17. echo 'stan ' . ($offset + 1) . '<br />';
  18.  
  19. if(++$offset == $success) {
  20.  
  21. return $i;
  22. }
  23.  
  24. } else {
  25. $i -= $offset;
  26. $offset = 0;
  27. }
  28.  
  29. return -1;
  30. }
  31.  
  32. if($ile = str_find('akjkhkj', 'alaalaalaalab') >= 0)
  33. echo 'Znaleziono!';
  34. else
  35. echo 'Nie znaleziono!';
  36.  
  37. ?>
Go to the top of the page
+Quote Post
nevt
post
Post #8





Grupa: Przyjaciele php.pl
Postów: 1 595
Pomógł: 282
Dołączył: 24.09.2007
Skąd: Reda, Pomorskie.

Ostrzeżenie: (0%)
-----


oczywiście, używając strstr()..... biggrin.gif biggrin.gif biggrin.gif


--------------------

-
Oh no, my young coder. You will find that it is you who are mistaken, about a great many things... -
Go to the top of the page
+Quote Post
SirZooro
post
Post #9





Grupa: Zarejestrowani
Postów: 243
Pomógł: 32
Dołączył: 14.06.2007

Ostrzeżenie: (0%)
-----


Cytat(hhg @ 20.11.2007, 13:23:21 ) *
da sie jeszcze ten kod jakkolwiek (doslownie jakkolwiek ) zoptymalizowac?

Google i zapytanie "algorytmy wyszukiwania podciągów" będzie pomocne - tutaj masz jeden z ciekawych wyników: http://pl.wikipedia.org/wiki/Kategoria:Algorytmy_tekstowe

Ten post edytował SirZooro 21.11.2007, 07:40:20


--------------------
Go to the top of the page
+Quote Post

Reply to this topicStart new topic
1 Użytkowników czyta ten temat (1 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Aktualny czas: 22.08.2025 - 10:05