给定一个s字符串和一个n字符串，在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1的算法设计

可以使用 KMP 算法来解决这个问题，该算法的时间复杂度为 $O(m+n)$，其中 $m$ 是 s 的长度，$n$ 是 n 的长度。

KMP 算法的核心是构建一个 next 数组，表示在匹配失败时，模式串应该向右移动的位置。

具体实现过程如下：

1. 构建 next 数组

首先，我们需要构建一个 next 数组。next 数组的长度为 n，其中 next[i] 表示当模式串的第 i 个字符与主串的某个字符不匹配时，模式串应该向右移动的位置。

next 数组的构建过程是从前往后遍历模式串，依次计算每一个位置的 next 值。具体实现如下：

def get_next(n: str) -> List[int]:
    next = [-1] * len(n)
    i, j = 0, -1
    while i < len(n) - 1:
        if j == -1 or n[i] == n[j]:
            i += 1
            j += 1
            next[i] = j
        else:
            j = next[j]
    return next

2. 在主串中查找模式串

接下来，我们可以使用 next 数组在主串中查找模式串。具体实现如下：

def kmp(s: str, n: str) -> int:
    next = get_next(n)
    i, j = 0, 0
    while i < len(s) and j < len(n):
        if j == -1 or s[i] == n[j]:
            i += 1
            j += 1
        else:
            j = next[j]
    if j == len(n):
        return i - j
    else:
        return -1

完整代码如下：

from typing import List

def get_next(n: str) -> List[int]:
    next = [-1] * len(n)
    i, j = 0, -1
    while i < len(n) - 1:
        if j == -1 or n[i] == n[j]:
            i += 1
            j += 1
            next[i] = j
        else:
            j = next[j]
    return next

def kmp(s: str, n: str) -> int:
    next = get_next(n)
    i, j = 0, 0
    while i < len(s) and j < len(n):
        if j == -1 or s[i] == n[j]:
            i += 1
            j += 1
        else:
            j = next[j]
    if j == len(n):
        return i - j
    else:
        return -1

使用示例：

s = "hello world"
n = "world"
print(kmp(s, n))  # 6

在这个例子中，模式串 "world" 在主串 "hello world" 中出现的位置是 6，因此 kmp 函数返回 6。