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";
}
?>

8 comments:

Denis said...

Tole bi moglo it čez

<?php

$s = '芞 Tolpa Natika Kita Na Plot žŠč';
$s = preg_replace('/\W+/iu', '', strtolower($s)); # http://www.php.net/manual/en/mbstring.overload.php !!

preg_match_all('/./us', $s, $m);
$r = implode('',array_reverse($m[0]));

var_dump($s, $r, $s == $r);

Tim Rijavec said...

Samo to ni palindrom, ker definicija palindroma je, da je zaporedje znakov z leve in z desne enako. Je treba tudi presledke upostevati.

Damijan said...

Ne smemo pozabiti tudi na velike in male crke.

Damijan said...

Evo sem popravil :)

Denis said...

@Tim -- wikipedia (http://en.wikipedia.org/wiki/Palindrome) pravi da pobereš ven ves šum (ločila, presledke)... "rats live on no evil star" je pač royal flush ;)

Tim Rijavec said...

Ma ne, ponavadi se presledke in ločila lahko ignorira, da lahko več stavkov interpretiramo kot validen palindrom ni pa res, da jih moraš. Torej je recimo v enem primeru "ab b a" validen palindrom v drugem pa ni.

Tim Rijavec said...

... da zaključiva, oba imava prav.

Denis said...

itak :) meni je prav.