String Matching

Quick Start Guide

String Matching Algorithms

Author : Robin Singh

Programs List :

1 . Knuth Morris Pratt String Matching Algorithm 2 . Naive Method 3 . Rabin Karp String Matching Algorithm

Knuth Morris Pratt

Example :

# import required algorithm
>>> from package.pygostructures.algorithms.string_matching import KnuthMorrisPratt

# string to be searched
>>> string1 = "csk"

# main string from which string 1 has to be searched
>>> string2 = "jadhgdajdkcsklsdhajhd"


>>> a = KnuthMorrisPratt(string1,string2)

>>> a.knuth_morris_pratt()
Pattern Found At Index :10

class pythorn.algorithms.string_matching.KnuthMorrisPratt(string1, string2)

Implementation Of KMP string Matching Algorithm

static prefix_generator(pattern, m, n)

utility function for generating prefix

knuth_morris_pratt()

Prints

prints the index if string is matched

static time_complexity()

Returns

time complexity

static get_code()

Returns

source code

Naive Method

Example :

# import required algorithm
>>> from pythorn.algorithms.string_matching import NaiveMethod

# string to be searched
>>> string1 = "in"

# main string from which string 1 has to be searched
>>> string2 = "djhdjhdinqwert"


>>> a = NaiveMethod(string1,string2)

>>> a.naive_method()
Pattern Found At Index :7

class pythorn.algorithms.string_matching.NaiveMethod(string1, string2)

Implementation Of Naive method string Matching Algorithm

naive_method()

Prints

prints index if string is matched

static time_complexity()

Returns

time complexity

static get_code()

Returns

source code

Rabin Karp

Example :

# import required algorithm
>>> from pythorn.algorithms.string_matching import RabinKarp

# string to be searched
>>> string1 = "in"

# main string from which string 1 has to be searched
>>> string2 = "djhdjhdinqwert"


>>> a = RabinKarp(string1,string2)

>>> a.rabin_karp()
Pattern Found At Index :7

class pythorn.algorithms.string_matching.RabinKarp(string1, string2)

Implementation Of Rabin Karp method string Matching Algorithm

rabin_karp()

Prints

prints index if string exists

static time_complexity()

Returns

time complexity

static get_code()

:return:source code