Wednesday, March 13, 2013

Palindromes search

The task is to find all the palindromes (spells the same from right and left) in the given text and print them with the number of occurrences. Minimum length of string is 2 since a character is a palindrome.

Here is an updated solution (thx Denis & Tim for pointing it out.):


<?php
// Given a string, test it for Palindromes, then output them along with the number of times they occur?
//sample string
$s = 'cd111 ana 876 qqqqqwq 00112 čćčćććččć把ŠŠđđđđđĐĐĐĐĐđččć';


//array to store results
$res = array();

mb_regex_encoding('UTF-8');
mb_internal_encoding('UTF-8');

//borrowed from http://www.codigomanso.com/en/2009/02/convert-utf8-string-to-array-in-php/
// using mb_check_encoding instead of mb_substr ;)
function getCharArray ($jstring) {
  if (mb_strlen($jstring, 'UTF-8') == 0)
    return array();

  $ret = array();
  $alen = strlen($jstring);
  $char = '';
  for ($i = 0; $i < $alen; $i++) {
    $char .= $jstring[$i];
    if (mb_check_encoding($char, 'UTF-8')) {
      array_push($ret, $char);
      $char = '';
    }
  }
  return $ret;
}

//mimumum lenght is 2
for ($l = 2; $l < mb_strlen($s) + 1; $l++) {
  //get all the posible subsrings with lenght above 2
  for ($i = 0; $i < (mb_strlen($s) + 1 - $l); $i++) {
    $g = mb_substr($s, $i, $l);

    //reverse $g string,
    //could use strrev but it is not multibyte safe
    //$rg = strrev($g);
    //multibyte safe version
    $t = getCharArray($g);
    $t = array_reverse($t);
    $rg = implode($t);

    //compare and store to result array
    if ($g == $rg) {
      //if match
      if (array_key_exists($g, $res)) {
        $res[$g] = $res[$g] + 1;
      }
      else {
        $res[$g] = 1;
      }
    }
  }
}

//output the results
foreach ($res as $r => $v) {
  echo "$r:$v\n";
}
?>
Post a Comment