# Path: pyalgs/algorithms/strings/substring_search.py
# class BruteForceSubstringSearch(SubstringSearch):
#     def __init__(self, pattern):
#         self.pattern = pattern
# 
#     def search_in(self, text):
#         n = len(text)
# 
#         for i in range(n - len(self.pattern)):
#             J = i
#             for j in range(len(self.pattern)):
#                 k = i + j
#                 if text[k] != self.pattern[j]:
#                     J = -1
#                     break
#             if J != -1:
#                 return J
# 
#         return -1
# 
# class RabinKarp(SubstringSearch):
#     patHash = None
#     Q = 1573773197
#     R = 256
#     M = None
#     RM = None
# 
#     def __init__(self, pat):
#         h = 1
#         self.M = len(pat)
#         for i in range(1, self.M):
#             h = (h * RabinKarp.R) % RabinKarp.Q
# 
#         self.RM = h
# 
#         self.patHash = self.hash(pat, self.M)
# 
#     def hash(self, text, M):
#         h = 0
#         for d in range(M):
#             h = (h * RabinKarp.R + char_at(text, d)) % RabinKarp.Q
#         return h
# 
#     def search_in(self, text):
#         text_hash = self.hash(text, self.M)
#         if text_hash == self.patHash:
#             return 0
#         for i in range(self.M, len(text)):
#             text_hash = (text_hash + RabinKarp.Q - self.RM * char_at(text, i - self.M) % RabinKarp.Q) % RabinKarp.Q
#             text_hash = (text_hash * RabinKarp.R + char_at(text, i)) % RabinKarp.Q
#             if text_hash == self.patHash:
#                 return i - self.M + 1
#         return -1
# 
# class BoyerMoore(SubstringSearch):
#     right = None
#     R = 256
#     pattern = None
# 
#     def __init__(self, pattern):
#         self.pattern = pattern
#         self.right = [0] * BoyerMoore.R
#         for i in range(len(pattern)):
#             self.right[char_at(pattern, i)] = i
# 
#     def search_in(self, text):
#         n = len(text)
#         m = len(self.pattern)
# 
#         skip = 1
#         i = 0
#         while i <= n - m:
#             for j in range(m-1, -1, -1):
#                 if char_at(text, i+j) != char_at(self.pattern, j):
#                     skip = max(1, j - self.right[char_at(text, i+j)])
#                     break
#                 if j == 0:
#                     return i
#             i += skip
# 
#         return -1
# 
# class KnuthMorrisPratt(SubstringSearch):
# 
#     dfs = None
#     M = None
#     R = 256
# 
#     def __init__(self, pattern):
#         self.M = len(pattern)
# 
#         self.dfs = [None] * self.R
#         for i in range(self.R):
#             self.dfs[i] = [0] * self.M
#         self.dfs[0][0] = 1
# 
#         X = 0
#         for j in range(self.M):
#             for i in range(self.R):
#                 self.dfs[i][j] = self.dfs[i][X]
#             self.dfs[char_at(pattern, j)][j] = j+1
#             X = self.dfs[char_at(pattern, j)][X]
# 
#     def search_in(self, text):
# 
#         n = len(text)
# 
#         j = 0
#         for i in range(n):
#             j = self.dfs[char_at(text, i)][j]
#             if j == self.M:
#                 return i - self.M
# 
#         return -1
# 
# Path: tests/algorithms/strings/util.py
# def some_text():
#     return "bed bug dad yes zoo now for tip ilk dim tag jot sob nob sky hut men egg few jay owl joy rap gig wee was wad fee tap tar dug jam all bad yet"


import unittest
from pyalgs.algorithms.strings.substring_search import BruteForceSubstringSearch, RabinKarp, BoyerMoore, \
    KnuthMorrisPratt
from tests.algorithms.strings.util import some_text



class BruteForceSubstringSearchUnitTest(unittest.TestCase):

    def test_search(self):
        t = some_text()
        ss = BruteForceSubstringSearch('men')
        self.assertNotEqual(-1, ss.search_in(t))
        self.assertEqual(-1, ss.search_in('Hello World'))


class RabinKarpUnitTest(unittest.TestCase):

    def test_search(self):
        t = some_text()
        ss = RabinKarp('men')
        self.assertNotEqual(-1, ss.search_in(t))
        self.assertEqual(-1, ss.search_in('Hello World'))


class BoyerMooreUnitTest(unittest.TestCase):

    def test_search(self):

# Path: pyalgs/algorithms/strings/substring_search.py
# class BruteForceSubstringSearch(SubstringSearch):
#     def __init__(self, pattern):
#         self.pattern = pattern
# 
#     def search_in(self, text):
#         n = len(text)
# 
#         for i in range(n - len(self.pattern)):
#             J = i
#             for j in range(len(self.pattern)):
#                 k = i + j
#                 if text[k] != self.pattern[j]:
#                     J = -1
#                     break
#             if J != -1:
#                 return J
# 
#         return -1
# 
# class RabinKarp(SubstringSearch):
#     patHash = None
#     Q = 1573773197
#     R = 256
#     M = None
#     RM = None
# 
#     def __init__(self, pat):
#         h = 1
#         self.M = len(pat)
#         for i in range(1, self.M):
#             h = (h * RabinKarp.R) % RabinKarp.Q
# 
#         self.RM = h
# 
#         self.patHash = self.hash(pat, self.M)
# 
#     def hash(self, text, M):
#         h = 0
#         for d in range(M):
#             h = (h * RabinKarp.R + char_at(text, d)) % RabinKarp.Q
#         return h
# 
#     def search_in(self, text):
#         text_hash = self.hash(text, self.M)
#         if text_hash == self.patHash:
#             return 0
#         for i in range(self.M, len(text)):
#             text_hash = (text_hash + RabinKarp.Q - self.RM * char_at(text, i - self.M) % RabinKarp.Q) % RabinKarp.Q
#             text_hash = (text_hash * RabinKarp.R + char_at(text, i)) % RabinKarp.Q
#             if text_hash == self.patHash:
#                 return i - self.M + 1
#         return -1
# 
# class BoyerMoore(SubstringSearch):
#     right = None
#     R = 256
#     pattern = None
# 
#     def __init__(self, pattern):
#         self.pattern = pattern
#         self.right = [0] * BoyerMoore.R
#         for i in range(len(pattern)):
#             self.right[char_at(pattern, i)] = i
# 
#     def search_in(self, text):
#         n = len(text)
#         m = len(self.pattern)
# 
#         skip = 1
#         i = 0
#         while i <= n - m:
#             for j in range(m-1, -1, -1):
#                 if char_at(text, i+j) != char_at(self.pattern, j):
#                     skip = max(1, j - self.right[char_at(text, i+j)])
#                     break
#                 if j == 0:
#                     return i
#             i += skip
# 
#         return -1
# 
# class KnuthMorrisPratt(SubstringSearch):
# 
#     dfs = None
#     M = None
#     R = 256
# 
#     def __init__(self, pattern):
#         self.M = len(pattern)
# 
#         self.dfs = [None] * self.R
#         for i in range(self.R):
#             self.dfs[i] = [0] * self.M
#         self.dfs[0][0] = 1
# 
#         X = 0
#         for j in range(self.M):
#             for i in range(self.R):
#                 self.dfs[i][j] = self.dfs[i][X]
#             self.dfs[char_at(pattern, j)][j] = j+1
#             X = self.dfs[char_at(pattern, j)][X]
# 
#     def search_in(self, text):
# 
#         n = len(text)
# 
#         j = 0
#         for i in range(n):
#             j = self.dfs[char_at(text, i)][j]
#             if j == self.M:
#                 return i - self.M
# 
#         return -1
# 
# Path: tests/algorithms/strings/util.py
# def some_text():
#     return "bed bug dad yes zoo now for tip ilk dim tag jot sob nob sky hut men egg few jay owl joy rap gig wee was wad fee tap tar dug jam all bad yet"


# Path: tests/algorithms/strings/substring_search_unit_test.py
import unittest
from pyalgs.algorithms.strings.substring_search import BruteForceSubstringSearch, RabinKarp, BoyerMoore, \
    KnuthMorrisPratt
from tests.algorithms.strings.util import some_text




class BruteForceSubstringSearchUnitTest(unittest.TestCase):

    def test_search(self):
        t = some_text()
        ss = BruteForceSubstringSearch('men')
        self.assertNotEqual(-1, ss.search_in(t))
        self.assertEqual(-1, ss.search_in('Hello World'))


class RabinKarpUnitTest(unittest.TestCase):

    def test_search(self):
        t = some_text()
        ss = RabinKarp('men')
        self.assertNotEqual(-1, ss.search_in(t))
        self.assertEqual(-1, ss.search_in('Hello World'))


class BoyerMooreUnitTest(unittest.TestCase):

    def test_search(self):

        t = some_text()