Algorithms

pydatastructs.find(text, query, algorithm)

Finds occurrence of a query string within the text string.

Parameters

• text (str) – The string on which query is to be performed.

• query (str) – The string which is to be searched in the text.

• algorithm (str) –

  The algorithm which should be used for searching. Currently the following algorithms are supported,

  ’kmp’ -> Knuth-Morris-Pratt as given in [1].

  ’rabin_karp’ -> Rabin–Karp algorithm as given in [2].

Returns

An array of starting positions of the portions in the text which match with the given query.

Return type

DynamicOneDimensionalArray

Examples

>>> from pydatastructs.strings.algorithms import find
>>> text = "abcdefabcabe"
>>> pos = find(text, "ab", algorithm="kmp")
>>> str(pos)
"['0', '6', '9']"
>>> pos = find(text, "abc", algorithm="kmp")
>>> str(pos)
"['0', '6']"
>>> pos = find(text, "abe", algorithm="kmp")
>>> str(pos)
"['9']"
>>> pos = find(text, "abed", algorithm="kmp")
>>> str(pos)
'[]'

References

1

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

2

https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm