Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!

Anagrams Within Words

By: jessecascio on Feb 22nd, 2014  |  syntax: PHP  |  size: 2.32 KB  |  views: 55  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }