How to search by skipping equidistant letters

gilgalbiblewheel · February 5, 2011, 7:27am

rpkamp:

Your code makes no sense at all. Below is an outline of how to do what you want. Please read it carefully to see if you understand it. Don’t just copy/paste and hope for the best.


$charToSearchFor='l';
$string='lovelovelovelovelove';
$pos=0;
$positions=array();
$continue=true;
while ($continue)
{
   if (false !== ($newPos=strpos($string, $charToSearchFor, $pos)))
   {
      $pos=$newPos+1;
      array_push($positions, $newPos);
   }
   else
   {
      $continue=false;
   }
}
var_dump($positions);
/**
array(5) {
  [0]=>
  int(0)
  [1]=>
  int(4)
  [2]=>
  int(8)
  [3]=>
  int(12)
  [4]=>
  int(16)
}
**/

$string="abclxoxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyelove";
$string_split=str_split($string);
$chars=str_split("love");
$charToSearchFor='l';

$pos=0;
$positions=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[0], $pos))){
		$pos=$newPos+1;
		array_push($positions, $newPos);
	}else{
		$continue=false;
	}
}
var_dump($positions);

$pos=0;
$positions2=array();
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[1], $pos))){
		$pos=$newPos+1;
		array_push($positions2, $newPos);
	}else{
		$continue=false;
	}
}
var_dump($positions2);

/*
for($i=0; $i<count($positions); $i++){
	echo $string_split[$positions[$i]]."<br />";
	for($j=0; $j<count($positions); $j++){
		echo $string_split[$positions[$i]]."<br />";
	
	}
}*/

Why does the second while loop show an empty array?
edit:
Ok never mind. $continue had to be rewritten for the 2nd while loop.
It’s not finished yet but does this make any sense?

$string="abclxoxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyelove";
$string_split=str_split($string);
$chars=str_split("love");
$charToSearchFor='l';

$pos=0;
$positions=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[0], $pos))){
		$pos=$newPos+1;
		array_push($positions, $newPos);
	}else{
		$continue=false;
	}
}
//var_dump($positions);

$pos=0;
$positions2=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[1], $pos))){
		$pos=$newPos+1;
		array_push($positions2, $newPos);
	}else{
		$continue=false;
	}
}
//var_dump($positions2);

echo $string."<br />";
for($i=0; $i<count($positions); $i++){
	//echo $string_split[$positions[$i]]."<br />";
	for($j=0; $j<count($positions2); $j++){
		$distance=$positions2[$j]-$positions[$i];
		//echo $distance.", ";
		for($k=0; $k<count($chars); $k++){
			if($string_split[$distance*$k]==$chars[2]){
				echo "<strong>".$distance.", ".$string_split[$distance*$k]."</strong>";
			}
		}
	}
	echo "<br />";
}

gilgalbiblewheel · February 5, 2011, 8:05am

Ok never mind. $continue had to be rewritten for the 2nd while loop.
It’s not finished yet but does this make any sense?

$string="abclxoxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyelove";
$string_split=str_split($string);
$chars=str_split("love");
$charToSearchFor='l';

$pos=0;
$positions=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[0], $pos))){
		$pos=$newPos+1;
		array_push($positions, $newPos);
	}else{
		$continue=false;
	}
}
//var_dump($positions);

$pos=0;
$positions2=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[1], $pos))){
		$pos=$newPos+1;
		array_push($positions2, $newPos);
	}else{
		$continue=false;
	}
}
//var_dump($positions2);

echo $string."<br />";
for($i=0; $i<count($positions); $i++){
	//echo $string_split[$positions[$i]]."<br />";
	for($j=0; $j<count($positions2); $j++){
		$distance=$positions2[$j]-$positions[$i];
		//echo $distance.", ";
		for($k=0; $k<count($chars); $k++){
			if($string_split[$distance*$k]==$chars[2]){
				echo "<strong>".$distance.", ".$string_split[$distance*$k]."</strong>";
			}
		}
	}
	echo "<br />";
}

I’m not sure how to continue after the if statement within the for loop of $k.
I want to see if the string_split[$distance*$k] meaning for example the 4th (4x1) letter after the 1st L is o and then the 8th (4x2) letter after L is v and then the 12th letter (4x3) is e. If so create an array and store them in the array. Otherwise go to the next $distance.

gilgalbiblewheel · February 5, 2011, 9:24am

I don’t know if this makes sense:

$string="abclxoxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyelove";
$string_split=str_split($string);
$chars=str_split("love");
$charToSearchFor='l';

$pos=0;
$positions=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[0], $pos))){
		$pos=$newPos+1;
		array_push($positions, $newPos);
	}else{
		$continue=false;
	}
}
echo "<br /><span style=\\"color: red;\\">".$chars[0]." = </span><br />";
var_dump($positions);

$pos=0;
$positions2=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[1], $pos))){
		$pos=$newPos+1;
		array_push($positions2, $newPos);
	}else{
		$continue=false;
	}
}
echo "<br /><span style=\\"color: red;\\">".$chars[1]." = </span><br />";
var_dump($positions2);
$pos=0;
$positions3=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[2], $pos))){
		$pos=$newPos+1;
		array_push($positions3, $newPos);
	}else{
		$continue=false;
	}
}
echo "<br /><span style=\\"color: red;\\">".$chars[2]." = </span><br />";
var_dump($positions3);
$pos=0;
$positions4=array();
$continue=true;
while ($continue){
	if (false !== ($newPos=strpos($string, $chars[3], $pos))){
		$pos=$newPos+1;
		array_push($positions4, $newPos);
	}else{
		$continue=false;
	}
}
echo "<br /><span style=\\"color: red;\\">".$chars[3]." = </span><br />";
var_dump($positions4);

echo $string."<br />";
for($i=0; $i<count($positions); $i++){
	for($j=0; $j<count($positions2); $j++){
		$distance=$positions2[$j]-$positions[$i];
		//echo "<span style=\\"color: red;\\"> ".$distance.", </span>";
		for($k=1; $k<count($chars)+1; $k++){
			if($string_split[$distance*$k-1]==$chars[$k-1]){
				echo "<span style=\\"font-weight: bold;\\">distance = <span style=\\"color: blue; font-weight: bold;\\">".$distance."</span>, <span style=\\"font-weight: bold;\\">letter</span> = <span style=\\"color: red; font-weight: bold;\\">".$string_split[$distance*$k-1]."</span>; ";
			}
		}
	}
	echo "<br />";
}

Output:

l =
array(15) { [0]=> int(3) [1]=> int(14) [2]=> int(21) [3]=> int(28) [4]=> int(39) [5]=> int(46) [6]=> int(53) [7]=> int(64) [8]=> int(71) [9]=> int(78) [10]=> int(89) [11]=> int(96) [12]=> int(103) [13]=> int(114) [14]=> int(121) }
o =
array(16) { [0]=> int(5) [1]=> int(7) [2]=> int(16) [3]=> int(22) [4]=> int(32) [5]=> int(41) [6]=> int(47) [7]=> int(57) [8]=> int(66) [9]=> int(72) [10]=> int(82) [11]=> int(91) [12]=> int(97) [13]=> int(107) [14]=> int(116) [15]=> int(122) }
v =
array(15) { [0]=> int(11) [1]=> int(18) [2]=> int(23) [3]=> int(36) [4]=> int(43) [5]=> int(48) [6]=> int(61) [7]=> int(68) [8]=> int(73) [9]=> int(86) [10]=> int(93) [11]=> int(98) [12]=> int(111) [13]=> int(118) [14]=> int(123) }
e =
array(15) { [0]=> int(15) [1]=> int(20) [2]=> int(24) [3]=> int(40) [4]=> int(45) [5]=> int(49) [6]=> int(65) [7]=> int(70) [8]=> int(74) [9]=> int(90) [10]=> int(95) [11]=> int(99) [12]=> int(115) [13]=> int(120) [14]=> int(124) } abclxoxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyelove
distance = 4, letter = l; distance = 4, letter = o; distance = 4, letter = v; distance = 4, letter = e; distance = 29, letter = l; distance = 29, letter = o; distance = 29, letter = v; distance = 29, letter = e; distance = 54, letter = l; distance = 54, letter = o; distance = 79, letter = l; distance = 104, letter = l;
distance = 8, letter = v; distance = 33, letter = v;

distance = 4, letter = l; distance = 4, letter = o; distance = 4, letter = v; distance = 4, letter = e; distance = 29, letter = l; distance = 29, letter = o; distance = 29, letter = v; distance = 29, letter = e; distance = 54, letter = l; distance = 54, letter = o; distance = 79, letter = l;
distance = 8, letter = v; distance = 33, letter = v;

distance = 4, letter = l; distance = 4, letter = o; distance = 4, letter = v; distance = 4, letter = e; distance = 29, letter = l; distance = 29, letter = o; distance = 29, letter = v; distance = 29, letter = e; distance = 54, letter = l; distance = 54, letter = o;
distance = 8, letter = v; distance = 33, letter = v;

distance = 4, letter = l; distance = 4, letter = o; distance = 4, letter = v; distance = 4, letter = e; distance = 29, letter = l; distance = 29, letter = o; distance = 29, letter = v; distance = 29, letter = e;
distance = 8, letter = v; distance = 33, letter = v;

distance = 4, letter = l; distance = 4, letter = o; distance = 4, letter = v; distance = 4, letter = e;
distance = 8, letter = v;

rpkamp · February 5, 2011, 9:58am

You are certainly on the right track, and your code makes sense, too!

However (there’s always that guy who has to say “however”), The problem with the code is that is written for 4 characters, so it won’t work it you want to search for more than 4, or less than 4 characters.
You’d need to rewrite it so that becomes generic and can look for any number of characters you feed it.
Take a good look at the code, find the repetition across the creation of $positions up until $positions4, and replace that repetition by more generic code.

gilgalbiblewheel · February 5, 2011, 10:49am

Well, I know that the while loop has to be within a for loop where $i<count($chars). But how would you handle the $positions? I think it should be in a sub array somehow.

AnthonySterling · February 5, 2011, 11:20am

Looking good!

How about something like.


<?php
$string  = 'abclxoxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvx';
$string .= 'xleoyvyeloveabclxxxoxxxvxxleoyvyeloveabclxxxoxxxvxxleoyvyelovee';

$occurrences = array();

$word = 'love';

foreach(str_split($string) as $pos => $chr){
  if($word[0] !== $chr){
    continue;
  }
  if($word === substr($string, $pos, strlen($word))){
    $occurrences[$pos] = array();
    for($i = 0; $i < strlen($word); $i++){
      $occurrences[$pos][ $word[$i] ] = $pos + $i;
    }
  }
}

var_dump(
  $occurrences
);

/*
  array(5) {
    [21]=>
    array(4) {
      ["l"]=>
      int(21)
      ["o"]=>
      int(22)
      ["v"]=>
      int(23)
      ["e"]=>
      int(24)
    }
    [46]=>
    array(4) {
      ["l"]=>
      int(46)
      ["o"]=>
      int(47)
      ["v"]=>
      int(48)
      ["e"]=>
      int(49)
    }
    [71]=>
    array(4) {
      ["l"]=>
      int(71)
      ["o"]=>
      int(72)
      ["v"]=>
      int(73)
      ["e"]=>
      int(74)
    }
    [96]=>
    array(4) {
      ["l"]=>
      int(96)
      ["o"]=>
      int(97)
      ["v"]=>
      int(98)
      ["e"]=>
      int(99)
    }
    [121]=>
    array(4) {
      ["l"]=>
      int(121)
      ["o"]=>
      int(122)
      ["v"]=>
      int(123)
      ["e"]=>
      int(124)
    }
  }
*/

rpkamp · February 5, 2011, 11:41am

Anthony, that doesn’t take into account that the letters have to be equidistant does it? Or am I missing something?

Yes indeed!


$string='lovexlxoxvxexxlxxoxxvxxe';
$word='love';
$chars=str_split($word);
$positions=array();
foreach ($chars as $i=>$char)
{
  $pos=0;
  $continue=true;
  $positions[$i]=array();
  while ($continue) {
    if (false !== ($newPos=strpos($string, $char, $pos))){
        $pos=$newPos+1;
        array_push($positions[$i], $newPos);
    } else {
        $continue=false;
    }
  }
}

var_dump($positions);

/**
array(4) { 
  [0]=>
  array(3) { // Char 0 -- L
    [0]=>
    int(0)
    [1]=>
    int(5)
    [2]=>
    int(14)
  }
  [1]=>
  array(3) { // Char 1 -- O
    [0]=>
    int(1)
    [1]=>
    int(7)
    [2]=>
    int(17)
  }
  [2]=>
  array(3) { // Char 2 - V
    [0]=>
    int(2)
    [1]=>
    int(9)
    [2]=>
    int(20)
  }
  [3]=>
  array(3) { // Char 3 - E
    [0]=>
    int(3)
    [1]=>
    int(11)
    [2]=>
    int(23)
  }
}
**/

Question is, what to do next?

AnthonySterling · February 5, 2011, 11:55am

Er, no.

So, we need to find the first character of the word, then the second, and if the subsequent characters appear at the same distance away from each other it’s a match?

We use the second character as the indicator to judge the distance for the rest?

rpkamp · February 5, 2011, 11:59am

Yes. Either that or build an array of all occurrences like I did in post #67 and check in there.
Both methods should work and yield the same results

Edit:

Scratch that, the array method is messed up. Brownie points for anyone who sees why

AnthonySterling · February 5, 2011, 8:08pm

Sweet!

It’s my first working implementation and it needs refactoring, but you’re more than welcome to it.


<?php
$string   = 'lovelovelovelove';
$word     = 'love';
$matches  = array();

for($pos = 0; $pos < strlen($string); $pos++)
{
  if($word[0] !== $string[$pos])
  {
    continue;
  }
  for($distance = 1; ($pos + $distance) < strlen($string); $distance++)
  {
    if($word[1] !== $string[$pos + $distance])
    {
      continue;
    }

    $search = '';

    for($i = 0; $i < strlen($word); $i++)
    {
      $search .= isset($string[$pos + ($i * $distance)]) ? $string[$pos + ($i * $distance)] : '' ;
    }

    if($word === $search)
    {
      $match = array();
      for($i = 0; $i < strlen($word); $i++)
      {
        $match[$string[$pos + ($i * $distance)]] = $pos + ($i * $distance) ;
      }
      array_push($matches, $match);
    }
  }
}

print_r(
  $matches
);

/*
Array
(
  [0] => Array
  (
    [l] => 0
    [o] => 1
    [v] => 2
    [e] => 3
  )
  [1] => Array
  (
    [l] => 0
    [o] => 5
    [v] => 10
    [e] => 15
  )
  [2] => Array
  (
    [l] => 4
    [o] => 5
    [v] => 6
    [e] => 7
  )
  [3] => Array
  (
    [l] => 8
    [o] => 9
    [v] => 10
    [e] => 11
  )
  [4] => Array
  (
    [l] => 12
    [o] => 13
    [v] => 14
    [e] => 15
  )
)
*/

gilgalbiblewheel · February 6, 2011, 6:19am

AnthonySterling:

Sweet!

It’s my first working implementation and it needs refactoring, but you’re more than welcome to it.


<?php
$string   = 'lovelovelovelove';
$word     = 'love';
$matches  = array();

for($pos = 0; $pos < strlen($string); $pos++)
{
  if($word[0] !== $string[$pos])
  {
    continue;
  }
  for($distance = 1; ($pos + $distance) < strlen($string); $distance++)
  {
    if($word[1] !== $string[$pos + $distance])
    {
      continue;
    }

    $search = '';

    for($i = 0; $i < strlen($word); $i++)
    {
      $search .= isset($string[$pos + ($i * $distance)]) ? $string[$pos + ($i * $distance)] : '' ;
    }

    if($word === $search)
    {
      $match = array();
      for($i = 0; $i < strlen($word); $i++)
      {
        $match[$string[$pos + ($i * $distance)]] = $pos + ($i * $distance) ;
      }
      array_push($matches, $match);
    }
  }
}

print_r(
  $matches
);

/*
Array
(
  [0] => Array
  (
    [l] => 0
    [o] => 1
    [v] => 2
    [e] => 3
  )
  [1] => Array
  (
    [l] => 0
    [o] => 5
    [v] => 10
    [e] => 15
  )
  [2] => Array
  (
    [l] => 4
    [o] => 5
    [v] => 6
    [e] => 7
  )
  [3] => Array
  (
    [l] => 8
    [o] => 9
    [v] => 10
    [e] => 11
  )
  [4] => Array
  (
    [l] => 12
    [o] => 13
    [v] => 14
    [e] => 15
  )
)
*/

This one’s good. BUt I need the negative results too. Such as:

[l] =&gt; 12

[o] =&gt; 9
[v] =&gt; 6
[e] =&gt; 3

I don’t understand where you’re splitting the $word or $string? But it works.

AnthonySterling · February 6, 2011, 9:31am

Thanks.

I don’t recall you stating you needed this functionality.

Either way, I’m going to leave that, minor issue, up to you to solve.

I don’t split them.

gilgalbiblewheel · February 7, 2011, 2:56am

Is there a function that turns a word backwards? Or is there a better solution than reusing this method only backward?

AnthonySterling · February 7, 2011, 7:29am

Seriously? You created a new post rather than search the manual, after all your/our work?

Barmy.

gilgalbiblewheel · February 7, 2011, 10:43am

ok. How do you search if php.net has such a function? What is it called?

rpkamp · February 7, 2011, 10:47am

A good place to start would be the list of string functions
And of course there is always google.

salathe · February 7, 2011, 11:29am

gilgalbiblewheel, am I correct in thinking that you really want to be searching with a hebrew word (not “love”) within hebrew text (not “xxlxxoxxvxxexx”), and all of the English letter use is just a big, ugly work-around?

gilgalbiblewheel · February 7, 2011, 11:15pm

yes

<?php
echo strrev("Hello world!"); // outputs "!dlrow olleH"
?>

Amit_Yaron · February 8, 2011, 7:39am

If you want to deal with the Hebrew letters of the string, use the function iconv. The description is found in '[URL=“http://nl3.php.net/manual/en/refs.international.php”]Human Language and Character Encoding Support’.
The character set for Hebrew is “ISO-8859-8”.
When you want to display your converted Hebrew text, to convert it back to “UTF-8”.

salathe · February 8, 2011, 9:33am

I’m not sure why you posted that code (it has nothing to do with my question) so here is another question for you.

Can you post an example (or multiple) of the string that needs to be searched, and some example search strings (I could make these up but best to make use of something that you will be using)? Because some text is RTL shouldn’t be cause for the kind of workarounds shown in this thread (though, it may be necessary depending on your needs).