python语言实现用分治法解决给定一个s字符串和一个n字符串，在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1（需要给出多个测试用例，证明算法的正确性）。

使用分治法解决字符串匹配问题相对困难，而且效率不一定高于暴力法。在此提供一种分治法的实现，供参考。

def match(s, n):
    s_len = len(s)
    n_len = len(n)
    if s_len < n_len:
        return -1
    if s == n:
        return 0
    if n_len == 1:
        for i in range(s_len):
            if s[i] == n:
                return i
        return -1
    mid = n_len // 2
    left = match(s, n[:mid])
    right = match(s, n[mid:])
    if left == -1 and right == -1:
        return -1
    elif left == -1:
        return right
    elif right == -1:
        return left
    else:
        return left

# 测试代码
s1 = "hello world"
n1 = "world"
assert match(s1, n1) == 6

s2 = "hello world"
n2 = "xx"
assert match(s2, n2) == -1

s3 = "hello world"
n3 = "hell"
assert match(s3, n3) == 0

s4 = "hello world"
n4 = "world!"
assert match(s4, n4) == -1

这个算法的基本思路是将模式串分成两半，递归地在主串中查找这两个子串，然后根据子串的查找结果来判断模式串在主串中的位置。如果两个子串都没有找到，说明模式串不存在于主串中，返回 -1。如果只有一个子串找到了，那么就返回这个子串在主串中的位置。如果两个子串都找到了，那么就返回左边子串在主串中的位置，因为左边子串出现在右边子串之前。

需要注意的是，这个算法的时间复杂度是 $O(nm\log m)$，其中 $n$ 是主串的长度，$m$ 是模式串的长度。在最坏情况下，即模式串中的字符都不相同，每次递归都需要遍历主串的全部字符，所以时间复杂度为 $O(nm\log m)$。当然，在实际应用中，模式串中的字符通常不会全部不相同，所以这个算法的实际时间复杂度可能比较难以估计。