jessecascio

Anagrams Within Words

Feb 22nd, 2014
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/php
  2. <?php
  3.  
  4. /**
  5.  * @since  February 22, 2014
  6.  * @see    http://programmingpraxis.com/2014/02/21/anagrams-within-words/
  7.  * @author http://jessesnet.com
  8.  *
  9.  * GOAL: Given two words, determine if the first word, or any anagram of it,
  10.  * appears in consecutive characters of the second word. For instance, cat appears
  11.  * as an anagram in the first three letters of actor, but car does not appear as an
  12.  * anagram in actor even though all the letters of car appear in actor.
  13.  *
  14.  * DESIGN: The algorithm design loops through each character of the word (minus the anagram length +1)
  15.  * and checks if the character is in the anagram.  If character is in anagram a segment
  16.  * (length of anagram) is taken from the word and validation is done to verify EACH letter
  17.  * of the anagram appears in the segment
  18.  *
  19.  * COMPLEXITY: n^2 * m
  20.  *   n = length of word
  21.  *   m = length of anagram
  22.  *
  23.  * EXAMPLES:
  24.  *   Anagram: cat
  25.  *   Word   : actor
  26.  *   Outcome: true
  27.  *
  28.  *   Anagram: car
  29.  *   Word   : actor
  30.  *   Outcome: false
  31.  *
  32.  */
  33.  
  34. $anagram = preg_replace('/[^a-z]/i', '', readline("Enter anagram: "));
  35. $word    = preg_replace('/[^a-z]/i', '', readline("Enter word: "));
  36.  
  37. var_dump(locate_anagram($anagram, $word));
  38.  
  39. /**
  40.  * Loop through word characters to see if anagram letters are present
  41.  */
  42. function locate_anagram($anagram, $word)
  43. {
  44.     if ($anagram == $word) {
  45.         return true;
  46.     }
  47.  
  48.     for ($i=0; $i<strlen($word)-strlen($anagram)+1; $i++) {
  49.  
  50.         if (strpos($anagram, $word[$i]) !== false) {
  51.            
  52.             $segment = substr($word, $i, strlen($anagram));
  53.  
  54.             if (verify_anagram($anagram, $segment)) {
  55.                 return true;
  56.             }
  57.         }
  58.     }
  59.  
  60.     return false;
  61. }
  62.  
  63. /**
  64.  * Loop through a phrase from the word to verify all anagram letters are present
  65.  */
  66. function verify_anagram($anagram, $segment)
  67. {  
  68.     if ($anagram == $segment) {
  69.         return true;
  70.     }
  71.  
  72.     $found = [];
  73.  
  74.     for ($j=0; $j<strlen($segment); $j++) {
  75.        
  76.         if (strpos($anagram, $segment[$j]) === false) {
  77.             return false;
  78.         }
  79.  
  80.         $found[] = $segment[$j];
  81.     }
  82.  
  83.     // check if segment and anagram have same chars
  84.     if (count(array_diff(str_split($anagram), $found))) {
  85.         return false;
  86.     }
  87.  
  88.     return true;
  89. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×