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

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:

[PHP] pobierz, plaintext 
<?php
 
function stringtoarray($string){
	$len = strlen($string);
 
	$cur = 0;
 
	$characterarray = array();
 
	while($cur < $len){
		$char = $string{$cur};
		array_push($characterarray,$char);
		$cur = $cur + 1;
	}
 
	return $characterarray;
}
 
 
	$belt = stringtoarray('ala ma kota');
	$search = stringtoarray('m*');
	$table = array();
 
	for ($j=0; $j<count($search); $j++)
		for ($i=0; $i<count($belt); $i++)
			$table[$j][$i] = 0;
 
	$j = 0;
 
		for ($i=0; $i<count($belt); $i++) {
 
			echo '- porownanie belt[' . $i . '] = ' . $belt[$i] . ', search[' . $j . '] = ' . $search[$j];
 
			if ($belt[$i] == $search[$j] || $search[$j] == '*') {
				$j++;
			} else {
				if ($j) $j--;
			}
 
 
			echo ' stan ' . $j . '<br />';
			$table[$j-1][$i] = $j;
 
			if ($j == count($search)) {
						echo 'znaleziono napis!<br />';
						$j = 0;
			}
 
			if ($j) echo '<br />';
		}
 
 
		echo '<br /><br />tablica przejsc: <br />nr poszczegolnych znakow / stany';
		for ($j=0; $j<count($search); $j++) {
			echo '<div style="float:left;"><pre>';
			var_dump($table[$j]);
			echo '</pre></div>';
		}
 
?>
[PHP] pobierz, plaintext 

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

[PHP] pobierz, plaintext 
<?php
 
function stringtoarray($string){
	$len = strlen($string);
 
	$cur = 0;
 
	$characterarray = array();
 
	while($cur < $len){
		$char = $string{$cur};
		array_push($characterarray,$char);
		$cur = $cur + 1;
	}
 
	return $characterarray;
}
 
 
	$belt = stringtoarray('ala ma kota');
	$search = stringtoarray('m*');
	$table = array();
 
	for ($j=0; $j<count($search); $j++)
		for ($i=0; $i<count($belt); $i++)
			$table[$j][$i] = 0;
 
	$j = 0;
 
		for ($i=0; $i<count($belt); $i++) {
 
			echo '- porownanie belt[' . $i . '] = ' . $belt[$i] . ', search[' . $j . '] = ' . $search[$j];
 
			if ($belt[$i] == $search[$j] || $search[$j] == '*') {
				$j++;
			} else {
				if ($j) {
					$j--;
					$i--;	 //tutaj
				}
			}
 
 
			echo ' stan ' . $j . '<br />';
			$table[$j-1][$i] = $j;
 
			if ($j == count($search)) {
						echo 'znaleziono napis!<br />';
						$j = 0;
			}
 
			if ($j) echo '<br />';
		}
 
 
		echo '<br /><br />tablica przejsc: <br />nr poszczegolnych znakow / stany';
		for ($j=0; $j<count($search); $j++) {
			echo '<div style="float:left;"><pre>';
			var_dump($table[$j]);
			echo '</pre></div>';
		}
 
?>
[PHP] pobierz, plaintext 

macie koledzy skłonność do komplikowania prostych rzeczy...

[PHP] pobierz, plaintext 
<?php
function str_find($search, $belt)
{
	$offset = 0;
	$success = strlen($search);
	$stop = strlen($belt);
	for($i=0; $i < $stop; $i++)
		if(($search{$offset} == $belt{$i}) or ($search{$offset} == '*'))
			if(++$offset == $success)
				return $i; //znaleziono, zwraca nr znaku w $belt gdzie zaczyna się $search
			else;
		else
		{
			  $i -= $offset; //wystarczy ta zamiana !!
			$offset = 0;
		}
	return -1; // nie znaleziono
}
 
if(str_find('a*a', 'kubala') >= 0)
	echo 'Znaleziono!';
else
	echo 'Nie znaleziono!';
?>
[PHP] pobierz, plaintext 

Powodzenia na zaliczeniu...

Twoja procedura nie dziala

[PHP] pobierz, plaintext 
<?php
if(str_find('lla', 'kuballla') >= 0)
	echo 'Znaleziono!';
else
	echo 'Nie znaleziono!'
?>
[PHP] pobierz, plaintext 

Nie znaleziono

Tu jest poprawny kod.

[PHP] pobierz, plaintext 
<?php
function str_find($search, $belt)
{
	for($i=0; $i<strlen($belt)-strlen($search)+1;$i++)
		for($j=0; $j<strlen($search); $j++)
			if(($belt{$i+$j} == $search{$j}) || ($search{$j} == '*'))
			   if ($j == strlen($search)-1) return $i;
			   else continue;
			else break;
	return -1;
}
?>
[PHP] pobierz, plaintext 

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.

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

da sie jeszcze ten kod jakkolwiek (doslownie jakkolwiek ) zoptymalizowac?

[PHP] pobierz, plaintext 
<?php
 
function str_find($search, $belt) {
 
	$offset = 0;
	$success = strlen($search);
	$stop = strlen($belt);
	$remember = null;
 
 
 
	for($i=0; $i < $stop; $i++)
		if(($search{$offset} == $belt{$i}) or ($search{$offset} == '*')) {
 
 
 
			echo 'stan ' . ($offset + 1) . '<br />';
 
			if(++$offset == $success) {
 
				return $i;
			}
 
		} else {
			  $i -= $offset;
			$offset = 0;
		}
 
	return -1;
}
 
	if($ile = str_find('akjkhkj', 'alaalaalaalab') >= 0)
		echo 'Znaleziono!';
	else
		echo 'Nie znaleziono!';
 
?>
[PHP] pobierz, plaintext 

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

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