Strings¶
A place for implementation of string algorithms
Features¶
- To see all the available functions in a module, you can just type
help()
with the module name as argument. For example,
>>> from pygorithm import strings
>>> help(strings)
Help on package pygorithm.strings in pygorithm:
NAME
pygorithm.strings - Collection of string methods and functions
PACKAGE CONTENTS
anagram
isogram
manacher_algorithm
palindrome
pangram
Anagram¶
- Functions and their uses
Author: OMKAR PATHAK Created On: 17th August 2017
-
pygorithm.strings.anagram.
is_anagram
(word, _list)[source]¶ ANAGRAM An anagram is direct word switch or word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once we are taking a word and a list. We return the anagrams of that word from the given list and return the list of anagrams else return empty list.
Parameters: - word – word
- _list – list of words
Returns: anagrams
Isogram¶
- Functions and their uses
Author: OMKAR PATHAK Created On: 17th August 2017
Palindrome¶
- Functions and their uses
Author: OMKAR PATHAK Created On: 17th August 2017
Pangram¶
- Functions and their uses
Author: OMKAR PATHAK Created On: 17th August 2017
Manacher’s Algorithm¶
- Functions and their uses
Author: OMKAR PATHAK Created at: 27th August 2017
-
pygorithm.strings.manacher_algorithm.
manacher
(string)[source]¶ Computes length of the longest palindromic substring centered on each char in the given string. The idea behind this algorithm is to reuse previously computed values whenever possible (palindromes are symmetric).
Example (interleaved string): i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 s # a # b # c # q # q # q # q # q # q # x # y # P 0 1 0 1 0 1 0 1 2 3 4 5 6 5 4 ?
^ ^ ^ ^mirror center current right
We’re at index 15 wondering shall we compute (costly) or reuse. The mirror value for 15 is 9 (center is in 12). P[mirror] = 3 which means a palindrome of length 3 is centered at this index. A palindrome of same length would be placed in index 15, if 15 + 3 <= 18 (right border of large parlindrome centered in 12). This condition is satisfied, so we can reuse value from index 9 and avoid costly computation.