strStr

Question

• leetcode: Implement strStr() | LeetCode OJ
• lintcode: lintcode - (13) strstr

Problem Statement

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Example

If source = "source" and target = "target", return -1.

If source = "abcdabcdefg" and target = "bcd", return 1.

Challenge

O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Clarification

Do I need to implement KMP Algorithm in a real interview?

• Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first.

题解

对于字符串查找问题，可使用双重 for 循环解决，效率更高的则为 KMP 算法。双重 for 循环的使用较有讲究，因为这里需要考虑目标字符串比源字符串短的可能。对目标字符串的循环肯定是必要的，所以可以优化的地方就在于如何访问源字符串了。简单直观的解法是利用源字符串的长度作为 for 循环的截止索引，这种方法需要处理源字符串中剩余长度不足以匹配目标字符串的情况，而更为高效的方案则为仅遍历源字符串中有可能和目标字符串匹配的部分索引。

Python

class Solution:
    def strStr(self, source, target):
        if source is None or target is None:
            return -1

        for i in range(len(source) - len(target) + 1):
            for j in range(len(target)):
                if source[i + j] != target[j]:
                    break
            else:  # no break
                return i
        return -1

• str自带方法

class Solution:
    def strStr(self, source, target):
        # write your code here
        if source is None or target is None:
            return -1
        return source.find(target)

• KMP

class Solution:
    # @param haystack, a string
    # @param needle, a string
    # @return a string or None
    # @KMP algorithms
    def ComputePrefixFunction(self, needle):
        Pi = [0 for i in range(len(needle))]
        m = len(needle)
        Pi[0] = 0
        k = 0
        for q in range(1, m):
            while k > 0 and needle[k] != needle[q]:
                k = Pi[k - 1]
            if needle[k] == needle[q]:
                k = k + 1
            Pi[q] = k
        return Pi

    def strStr(self, haystack, needle):
        n = len(haystack)
        m = len(needle)
        if m == 0:
            return haystack
        Pi = self.ComputePrefixFunction(needle)
        q = 0
        for i in range(0, n):
            while q > 0 and needle[q] != haystack[i]:
                q = Pi[q - 1]
            if needle[q] == haystack[i]:
                q = q + 1
            if q == m:
                return haystack[i - m + 1:]
        return None

• 其他

  源码分析

• 边界检查：haystack(source)和needle(target)有可能是空串。

• 边界检查之下标溢出：注意变量i的循环判断条件，如果用的是i < source.length()则在后面的source.charAt(i + j)时有可能溢出。
• 代码风格：
  • 运算符==两边应加空格
  • 变量名不要起s1``s2这类，要有意义，如target``source
  • Java 代码的大括号一般在同一行右边，C++ 代码的大括号一般另起一行
  • int i, j;`声明前有一行空格，是好的代码风格
• 是否在for的条件中声明i,j，这个视情况而定，如果需要在循环外再使用时，则须在外部初始化，否则没有这个必要。

需要注意的是有些题目要求并不是返回索引，而是返回字符串，此时还需要调用相应语言的substring方法。Python3 中用range替换了xrange，Python2 中使用xrange效率略高一些。 另外需要注意的是 Python 代码中的else接的是for 而不是if, 其含义为no break, 属于比较 Pythonic 的用法，有兴趣的可以参考 4. More Control Flow Tools 的 4.4 节和 if statement - Why does python use 'else' after for and while loops?

复杂度分析

双重 for 循环，时间复杂度最坏情况下为 $$O((n-m)*m)$$.