给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1,算法分析
时间: 2024-05-18 10:16:08 浏览: 84
可以使用双指针算法来解决这个问题。首先,我们用两个指针 i 和 j 分别指向 s 和 n 的开头。然后我们开始遍历 s 字符串,如果当前 s[i] 和 n[j] 相等,则将 i 和 j 都向后移动一位。如果 j 移动到了 n 字符串的结尾,则说明我们已经找到了 n 字符串在 s 字符串中第一次出现的位置,即 i - j。如果 s[i] 和 n[j] 不相等,则将 i 移动到 i - j + 1 的位置,j 重置为 0。如果遍历完 s 字符串仍然没有找到 n 字符串,则返回 -1。
时间复杂度为 O(m+n),其中 m 和 n 分别为 s 和 n 字符串的长度。
阅读全文