文字列アルゴリズム

def brute_force(s, t):
    matched_indices = []
    n = len(s)
    m = len(t)

    for i in range(n - m + 1):
        for j in range(m):
            if s[i + j] != t[j]:
                break
        else:
            matched_indices.append(i)
    return matched_indices

1つ見つかったら終了ではなく一致箇所全てを求めるため、テーブルサイズを1つ長くし、最後まで一致した後に次に合わせるべき位置も計算している。

def make_kmp_table(t):
    i = 2
    j = 0
    m = len(t)
    tbl = [0] * (m + 1)
    tbl[0] = -1
    while i <= m:
        if t[i - 1] == t[j]:
            tbl[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = tbl[j]
        else:
            tbl[i] = 0
            i += 1
    return tbl


def kmp(s, t):
    matched_indices = []
    tbl = make_kmp_table(t)
    i = 0
    j = 0
    n = len(s)
    m = len(t)
    while i + j < n:
        if t[j] == s[i + j]:
            j += 1
            if j == m:
                matched_indices.append(i)
                i += j - tbl[j]
                j = tbl[j]
        else:
            i += j - tbl[j]
            if j > 0:
                j = tbl[j]
    return matched_indices

1対1の検索なら、まず $T$ をハッシュ化し、その後 $S$ をずらしてハッシュ化する過程で照合すればよい。僅かだがリスト化などの生成コストが抑えられる。 Pythonは多倍長整数を扱えるので、特別な書き方をしなくても $X,M$ に比較的大きな値を設定できる。

def rabin_karp(s, t):
    def exe(x, m):
        th = 0
        for c in tt:
            th = (th * x + c) % m

        sh = 0
        for c in st[:l]:
            sh = (sh * x + c) % m
        xl = pow(x, l - 1, m)

        matched = set()
        if sh == th:
            matched.add(0)
        for i, (c0, c1) in enumerate(zip(st, st[l:]), start=1):
            sh = ((sh - c0 * xl) * x + c1) % m
            if sh == th:
                matched.add(i)

        return matched

    l = len(t)
    st = list(map(ord, s))
    tt = list(map(ord, t))
    # Xはなるべくst,ttの最大要素より大きくする
    # Mはとりあえず2^61-1(素数)を設定する
    xs = random.sample(range(10 ** 9, 10 ** 10), 3)
    ans = exe(xs[0], 2305843009213693951)
    ans.intersection_update(exe(xs[1], 2305843009213693951))
    ans.intersection_update(exe(xs[2], 2305843009213693951))
    return sorted(ans)

from collections import deque


class AhoCorasick:

    def __init__(self, needles):
        self.children = [{}]
        self.match = [[]]

        for needle in needles:
            self._register(needle)

        self.failure = self._create_failure()

    def _register(self, needle):
        k = 0
        for c in needle:
            if c in self.children[k]:
                k = self.children[k][c]
            else:
                j = len(self.children)
                self.children[k][c] = j
                self.children.append({})
                self.match.append([])
                k = j
        self.match[k].append(needle)

    def _create_failure(self):
        children = self.children
        match = self.match
        failure = [0] * len(children)

        q = deque()
        for k in children[0].values():
            failure[k] = 0
            q.append(k)

        while q:
            k = q.popleft()
            for c, j in children[k].items():
                b = failure[k]
                failure[j] = self._get_next(b, c, failure)
                match[j].extend(match[failure[j]])
                q.append(j)

        return failure

    def _get_next(self, k, c, failure):
        while True:
            if c in self.children[k]:
                return self.children[k][c]
            if k == 0:
                return 0
            k = failure[k]

    def search(self, haystack):
        match = self.match

        k = 0
        matched = []
        for i, c in enumerate(haystack):
            k = self._get_next(k, c, self.failure)
            for m in match[k]:
                matched.append((i - len(m) + 1, i, m))
        return matched


ahc = AhoCorasick(['ab', 'bc', 'bab', 'd', 'ababcde', 'bababcde'])
print(ahc.search('xbababcdex'))
# => [(1, 3, 'bab'), (2, 3, 'ab'), (3, 5, 'bab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]