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

pygorithm.strings.anagram.get_code()[source]

returns the code for the is_anagram function :return: source code

Isogram

  • Functions and their uses

Author: OMKAR PATHAK Created On: 17th August 2017

pygorithm.strings.isogram.is_isogram(word)[source]

An isogram (also known as a “nonpattern word”) is a logological term for a word or phrase without a repeating letter

Parameters:word – word to check
Returns:bool
pygorithm.strings.isogram.get_code()[source]

returns the code for the is_isogram function :return: source code

Palindrome

  • Functions and their uses

Author: OMKAR PATHAK Created On: 17th August 2017

pygorithm.strings.palindrome.is_palindrome(string)[source]

Checks the string for palindrome

Parameters:string – string to check
Returns:true if string is a palindrome false if not
pygorithm.strings.palindrome.get_code()[source]

returns the code for the is_palindrome function :return: source code

Pangram

  • Functions and their uses

Author: OMKAR PATHAK Created On: 17th August 2017

pygorithm.strings.pangram.is_pangram(sentence)[source]

A sentence containing every letter of the alphabet.

Parameters:sentence – Sentence to check
Returns:bool
pygorithm.strings.pangram.get_code()[source]

returns the code for the is_pangram function :return: source code

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.

pygorithm.strings.manacher_algorithm.get_code()[source]

returns the code for the manacher’s algorithm :return: source code