# Anagrams Within Words

Feb 22nd, 2014
116
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. }