题目：28.找出字符串中第一个匹配项的下标

**题目:** 找出字符串中第一个匹配项的下标**问题描述:**

给定两个字符串 `s1` 和 `s2`,要求找出在 `s1` 中第一个匹配 `s2` 的位置。也就是说，找到第一个出现于 `s1` 中的 `s2` 的子串。

**示例:**

* 输入:`s1 = "hello world", s2 = "world"`
输出:`3`
* 输入:`s1 = "abcde", s2 = "cde"`
输出:`2`

**解决方案:**

我们可以使用 KMP 算法来解决这个问题。KMP 算法是一种线性时间复杂度的字符串匹配算法。

###1. KMP 算法首先，我们需要了解 KMP 算法的基本原理：

* **前缀函数:** 给定一个模式串 `s2`,我们可以计算出它的前缀函数 `pi`。前缀函数 `pi[i]` 表示的是，当前位置 `i` 的前缀子串是不是也能匹配模式串 `s2` 的前 `i` 个字符。
* **坏匹配:** 当我们在主串 `s1` 中匹配模式串 `s2` 时，如果匹配到某个位置后，发现不再匹配，我们就称这个位置为坏匹配。坏匹配的位置是关键，因为它决定了我们是否需要回溯。
* **回溯:** 当我们遇到坏匹配时，我们可以利用前缀函数 `pi` 来回溯。具体来说，如果当前位置 `i` 是坏匹配，那么我们就从 `i - pi[i]` 的位置开始匹配模式串 `s2`。

###2. 实现 KMP 算法下面是实现 KMP 算法的 Python代码：

def compute_prefix_function(s):
 """
 Compute the prefix function for a given string s.
 Args:
 s (str): The input string.
 Returns:
 list: The prefix function pi.
 """
 m = len(s)
 pi = [0] * m # Initialize the first element of pi j =0 for i in range(1, m):
 while j >0 and s[i] != s[j]:
 j = pi[j -1]
 if s[i] == s[j]:
 j +=1 pi[i] = j return pidef kmp_search(s1, s2):
 """
 Search for the first occurrence of a substring s2 in a string s1 using KMP algorithm.
 Args:
 s1 (str): The main string.
 s2 (str): The pattern string.
 Returns:
 int: The index of the first occurrence of s2 in s1, or -1 if not found.
 """
 pi = compute_prefix_function(s2)
 m, n = len(s2), len(s1)
 j =0 for i in range(n):
 while j >0 and s1[i] != s2[j]:
 j = pi[j -1]
 if s1[i] == s2[j]:
 j +=1 # If we've matched the entire pattern string, return the index if j == m:
 return i - m +1 # If we haven't found a match, return -1 return -1# Example usages1 = "hello world"
s2 = "world"

index = kmp_search(s1, s2)
print("The index of the first occurrence of '{}' in '{}' is {}".format(s2, s1, index))

# Test casestest_cases = [
 ("hello world", "world"),
 ("abcde", "cde"),
 ("abcdef", "def")
]

for s1, s2 in test_cases:
 index = kmp_search(s1, s2)
 print("Testing '{}' in '{}': Index = {}".format(s2, s1, index))