PythonによるKnuth-Morris-Pratt (KMP)アルゴリズムの実装です：

```
    def partial_match_table(pattern):
        """Compute the partial match table (also known as failure function) for the given pattern."""
        n = len(pattern)
        table = [0] * n
        i = 1
        j = 0
        while i < n:
            if pattern[i] == pattern[j]:
                j += 1
                table[i] = j
                i += 1
            elif j > 0:
                j = table[j-1]
            else:
                table[i] = 0
                i += 1
        return table

    def kmp(text, pattern):
        """Search for the given pattern in the given text using the Knuth-Morris-Pratt algorithm."""
        n = len(text)
        m = len(pattern)
        if m == 0:
            return 0
        table = partial_match_table(pattern)
        i = 0
        j = 0
        while i < n:
            if text[i] == pattern[j]:
                if j == m - 1:
                    return i - j
                i += 1
                j += 1
            elif j > 0:
                j = table[j-1]
            else:
                i += 1
        return -1
```

partial_match_table 関数は、与えられたパターンの部分一致テーブルを計算します。kmp関数は、KMPアルゴリズムを用いてテキスト中のパターンを検索します。部分一致テーブルを使用して、不一致が見つかったときにパターンを効率的に右にシフトします。

kmp 関数を使用するには、次のようにテキストとパターンを引数として渡します：

```
    text = "ababcabcabababd"
    pattern = "ababd"
    index = kmp(text, pattern)
    print(index)  # outputs: 10
```

この例では、kmp 関数はテキスト内で最初に出現するパターンのインデックスを返します。
Here is an implementation of the Knuth-Morris-Pratt (KMP) algorithm in Python:

    def partial_match_table(pattern):
        """Compute the partial match table (also known as failure function) for the given pattern."""
        n = len(pattern)
        table = [0] * n
        i = 1
        j = 0
        while i < n:
            if pattern[i] == pattern[j]:
                j += 1
                table[i] = j
                i += 1
            elif j > 0:
                j = table[j-1]
            else:
                table[i] = 0
                i += 1
        return table

    def kmp(text, pattern):
        """Search for the given pattern in the given text using the Knuth-Morris-Pratt algorithm."""
        n = len(text)
        m = len(pattern)
        if m == 0:
            return 0
        table = partial_match_table(pattern)
        i = 0
        j = 0
        while i < n:
            if text[i] == pattern[j]:
                if j == m - 1:
                    return i - j
                i += 1
                j += 1
            elif j > 0:
                j = table[j-1]
            else:
                i += 1
        return -1


The partial_match_table function computes the partial match table for the given pattern. The kmp function searches for the pattern in the text using the KMP algorithm. It uses the partial match table to efficiently shift the pattern to the right when a mismatch is found.

To use the kmp function, simply pass in the text and pattern as arguments, like so:


    text = "ababcabcabababd"
    pattern = "ababd"
    index = kmp(text, pattern)
    print(index)  # outputs: 10

In this example, the kmp function returns the index of the first occurrence of the pattern in the text, which is 10.