String Algorithms

1. anagram (a word or phrase made by transposing the letters of another word or phrase)

Question: Find all the anagrams in a dictionary
Solution: 1) Sign each word in the dictionary so that words in the same anagram class have the same signature, and then 2) bring together words with equal signatures. A signature scheme based on sorting is as follow: order the letters within the word alphabetically. To bring together, we can sort the words in the order of their signatures.

2. Palindrome ( a word, verse, or sentence (as *Able was I ere I saw Elba*) or a number (as 1881) that reads the same backward or forward)

3. String rotation without extra memory, used in text editor (move lines)

For example, abcdefg -> efgabcd. Step 1: Reverse the substring separately. abcdefg->dcbagfe Step 2: Reverse the whole string: dcbagfe->efgabcd