给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(需要给出多个测试用例,证明算法的正确性)用回溯法写出问题分析

问题分析：

这是一个经典的字符串匹配问题，可以使用回溯法来解决。回溯法是一种暴力搜索的算法，通过逐步试探，当发现当前解不可行时，就回溯到上一步，重新尝试其他可能的解。在字符串匹配问题中，我们可以通过遍历主串和子串，逐个比较字符是否相等来寻找匹配点。

算法流程：

1. 遍历主串 s，从第一个字符开始，逐个与子串 n 的第一个字符比较，找到第一个相同的字符。

2. 如果找到了相同的字符，比较 s 中该字符后面的子串是否与 n 相等，如果相等，则找到了匹配点，返回该位置；如果不相等，则回溯到上一步，重新从 s 中下一个字符开始比较。

3. 如果遍历完整个主串 s，还没有找到匹配点，说明不存在该子串，返回 -1。

证明算法的正确性：

我们可以通过多个测试用例来证明算法的正确性，例如：

1. s = "hello world", n = "world"，预期结果为 6。

2. s = "hello world", n = "hello"，预期结果为 0。

3. s = "hello world", n = "worlds"，预期结果为 -1。

4. s = "aaaaaaa", n = "aa"，预期结果为 0。

5. s = "abababab", n = "bab"，预期结果为 1。

以上测试用例均可以通过回溯法得到正确的结果。

代码实现：

以下是使用 Python 语言实现的回溯法代码：

def findSubstring(s, n):
    if not s or not n or len(s) < len(n):
        return -1
    i, j = 0, 0
    while i < len(s) and j < len(n):
        if s[i] == n[j]:
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0
    if j == len(n):
        return i - j
    else:
        return -1

该代码先判断输入的 s 和 n 是否为空或 s 的长度小于 n 的长度，如果是，则返回 -1。然后使用两个指针 i 和 j 分别遍历 s 和 n，如果当前字符相等，则 i 和 j 都加 1，否则回溯到上一步重新开始比较。最后判断是否找到了匹配点，如果是，则返回该位置，否则返回 -1。