首页 > itarticle > leetcode28. implement strstr() KMP算法 总结

leetcode28. implement strstr() KMP算法 总结

admin 11月 14, 2020 0

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
 
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
 
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf()).

思路

  1. 如果是pattern是空，返空。
  2. 如果pattern比text还要长，返-1。
  3. 从text的0开始遍历，一直到text剩下的字符串等于pattern的时候为止。不用遍历到text的末尾，这样可以提高效率。

My code in cpp

naive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
int (string haystack, string needle) {
    int p = needle.size(), t = haystack.size();
    if (!p) return 0;
    if (p>t) return -1;
    for (int index = 0; index <= t - p; index++)
    {
        for (int i=index,j = 0; j < p; j++,i++)
        {
            if (haystack[i] != needle[j])
                break;
            if (j == p-1)
                return index;
        } 
    } 
    return -1;
}

KMP算法

coming soon~~

总结

  1. 字符串匹配问题
  2. 暴力搜索法 O(m*n)
  3. KMP算法O(m+n)
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能