def string_matching_naive(text='', pattern=''):

"""Returns positions where pattern is found in text.

We slide the string to match 'pattern' over the text

O((n-m)m)

Example: text = 'ababbababa', pattern = 'aba'

string_matching_naive(t, s) returns [0, 5, 7]

@param text text to search inside

@param pattern string to search for

@return list containing offsets (shifts) where pattern is found inside text

"""

n = len(text)

m = len(pattern)

offsets = []

for i in range(n-m+1):

if pattern == text[i:i+m]:

offsets.append(i)

return offsets

def string_matching_rabin_karp(text='', pattern='', hash_base=256):

"""Returns positions where pattern is found in text.

worst case: O(nm)

O(n+m) if the number of valid matches is small and the pattern is large.

Performance: ord() is slow so we shouldn't use it here

Example: text = 'ababbababa', pattern = 'aba'

string_matching_rabin_karp(text, pattern) returns [0, 5, 7]

@param text text to search inside

@param pattern string to search for

@param hash_base base to calculate the hash value

@return list containing offsets (shifts) where pattern is found inside text

"""

n = len(text)

m = len(pattern)

offsets = []

htext = hash_value(text[:m], hash_base)

hpattern = hash_value(pattern, hash_base)

for i in range(n-m+1):

if htext == hpattern:

if text[i:i+m] == pattern:

offsets.append(i)

if i < n-m:

htext = (hash_base *

(htext -

(ord(text[i]) *

(hash_base ** (m-1))))) + ord(text[i+m])

return offsets

def hash_value(s, base):

"""Calculate the hash value of a string using base.

Example: 'abc' = 97 x base^2 + 98 x base^1 + 99 x base^0

@param s string to compute hash value for

@param base base to use to compute hash value

@return hash value

"""

v = 0

p = len(s)-1

for i in range(p+1):

v += ord(s[i]) * (base ** p)

p -= 1

return v

def string_matching_knuth_morris_pratt(text='', pattern=''):

"""Returns positions where pattern is found in text.

O(m+n)

Example: text = 'ababbababa', pattern = 'aba'

string_matching_knuth_morris_pratt(text, pattern) returns [0, 5, 7]

@param text text to search inside

@param pattern string to search for

@return list containing offsets (shifts) where pattern is found inside text

"""

n = len(text)

m = len(pattern)

offsets = []

pi = compute_prefix_function(pattern)

q = 0

for i in range(n):

while q > 0 and pattern[q] != text[i]:

q = pi[q - 1]

if pattern[q] == text[i]:

q = q + 1

if q == m:

offsets.append(i - m + 1)

q = pi[q-1]

return offsets

def compute_prefix_function(p):

m = len(p)

pi = [0] * m

k = 0

for q in range(1, m):

while k > 0 and p[k] != p[q]:

k = pi[k - 1]

if p[k] == p[q]:

k = k + 1

pi[q] = k

return pi

def string_matching_boyer_moore_horspool(text='', pattern=''):

"""Returns positions where pattern is found in text.

O(n)

Performance: ord() is slow so we shouldn't use it here

Example: text = 'ababbababa', pattern = 'aba'

string_matching_boyer_moore_horspool(text, pattern) returns [0, 5, 7]

@param text text to search inside

@param pattern string to search for

@return list containing offsets (shifts) where pattern is found inside text

"""

m = len(pattern)

n = len(text)

offsets = []

if m > n:

return offsets

skip = []

for k in range(256):

skip.append(m)

for k in range(m-1):

skip[ord(pattern[k])] = m - k - 1

skip = tuple(skip)

k = m - 1

while k < n:

j = m - 1

i = k

while j >= 0 and text[i] == pattern[j]:

j -= 1

i -= 1

if j == -1:

offsets.append(i + 1)

k += skip[ord(text[k])]

return offsets

def atoi(s):

"""Convert string to integer without doing int(s).

'123' -> 123

@param s string to convert.

@returns integer

"""

if not s:

raise ValueError

i = 0

idx = 0

neg = False

if s[0] == '-':

neg = True

idx += 1

for c in s[idx:]:

i *= 10

i += int(c)

if neg:

i = -i

return i

def reverse_string_words(s):

"""Reverse words inside a string (in place).

Since strings are immutable in Python, we copy the string chars to a list

first.

'word1 word2 word3' -> 'word3 word2 word1'

Complexity: O(n)

@param s string words to reverse.

@returns reversed string words.

"""

def reverse(l, i, j):

# 'word1' -> '1drow'

# Complexity: O(n/2)

while i != j:

l[i], l[j] = l[j], l[i]

i += 1

j -= 1

w = [e for e in s]

i = 0

j = len(w) - 1

reverse(w, i, j)

i = 0

j = 0

while j < len(w):

while j < len(w) and w[j] != ' ':

j += 1

reverse(w, i, j-1)

i = j + 1

j += 1

return ''.join(e for e in w)