Implement strStr

LeetCode笔记 阅读(305)

编号 : 28      
难度 : <font color="green">Easy</font>

# 题目 :  
>Implement strStr().
>
>Return the index of the first occurrence of `needle` in haystack, or **-1** if needle is not part of haystack.
>
>**Example 1**:
>
>>**Input**: haystack = "hello", needle = "ll"  
>>**Output**: 2
>
>**Example 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()`.

# 解 :  
```Cpp
class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i < haystack.size(); i++)
        {
            bool same = true;
            for(int j = 0; j <needle.size(); j++)
            {
                if(haystack[i+j] != needle[j])
                {
                    same = false;
                    break;
                }
            }

            if(same)
                return i;
        }

        if(needle.size() == 0)
            return 0;
        else
            return -1;
    }
};
```

# 分析 :  
题目要求从字符串中查找子串,返回第一个匹配的子串的索引,如果没找到则返回`-1`,如果目标子串为空字符串,则返回`0`。

上述解法采取暴力搜索的方式查找子串,复杂度为`O(n*m)`,`n`和`m`分别为两个字符串的长度。

## KMP算法
暴力求解时,每当发现不匹配,就将主串的搜索位置向后移动一位,时间复杂度为`O(n*m)`,非常慢。

观察下面例子(`i`和`j`指示正在比较的位置) :  

```
                       i
                       |
haystack : ...abcxxxabcx... 
needle   :    abcxxxabcy
                       |
                       j
```

这里发生了失配,但是可以看到,已匹配部分(`abcxxxabc`)中**末尾**的`abc`,与目标串**开头**的`abc`匹配,因此可以做如下移动 :  

```
                       i
                       |
haystack : ...abcxxxabcx... 
needle   :          abcxxxabcy
                       |
                       j
```

然后继续比较,即令`j = 3`而`i`不变。

>当比较过程中发生失配时,在该位置之前的已经匹配的部分如果存在**公共前后缀**(即上例中的`abc`),则可以令`j`等于**公共前后缀的长度**,而`i`不变,继续比较。
>* **公共前后缀**可能不止一个,而选择**最长**的那个可以减少最多的运算。
>* **公共前后缀**不能等于**已经匹配的部分**,如上例中不能选取`abcxxxabc`作为最长公共前后缀。
>* 如果没有**公共前后缀**,则`j = 0`。
>* 如果第0位就失配了,则`i++`。

由此可以根据目标串计算出每一个位置失配时,`j`应该是几 :  
```Cpp
/*
 * needle : 目标串
 * next : 返回参数 next[x]表示在x位置失配时,j应该赋值为几
 */
void getNext(std::string& needle, std::vector<int>& next)
{
    /* next的长度显然和needle一样,全体初始化为0 */
    next.clear();
    next.resize(needle.size(), 0);
    for(int x = 1; x < needle.size(); x++)
    {
        // 在x位置失配,搜索x前面的最长公共前后缀
        for(int y = 1; y < x; y++)
        {
            // 读取长度为y的前缀和后缀
            std::string prefix = needle.substr(0, y);
            std::string suffix = needle.substr(x - y, y);

            // 如果前后缀相同,则将长度存入next数组
            if(prefix == suffix)
            {
                next[x] = y;
            }
            // 循环继续进行,找有没有更长的
        }
    }
}
```

由此可以得出`abcxxxabc`的`next`数组值依次为`0, 0, 0, 0, 0, 0, 0, 1, 2, 3`

上述计算`next`数组的代码比较直观,但是效率不高,参考下面过程 :  

```
prefix   i
         |
needle : abcxxxabcy
          |
suffix    j
```

> 以此为初始状态开始搜索,由于前后缀不能等于整个串,所以让前缀索引从0开始,而后缀索引从1开始
>* 如果第0位失配,则`j++`,`next[0]`是无意义的
>* 如果第1位失配,显然没有公共前后缀,`next[1] = 0`


由于`needle[i] != needle[j]`,所以`next[2] = 0`,继续查找`j`后移。直到 :  

```
prefix   i
         |
needle : abcxxxabcyxxx
               |
suffix         j
```

第一次出现`needle[i] == needle[j]`,所以`next[j+1] = i + 1 = 1`,继续 :  
> `next[j+1]` 等于公共前后缀的长度,而前缀的长度为`i + 1`

```
prefix    i
          |
needle : abcxxxabcyxxx
                |
suffix          j
```

这次`i`也开始后移,仍有`needle[i] == needle[j]`,所以`next[j+1] = i + 1 = 2`

```
prefix     i
           |
needle : abcxxxabcyxxx
                 |
suffix           j
```
仍有`needle[i] == needle[j]`,所以`next[j+1] = 3`

```
prefix      i
            |
needle : abcxxxabcyxxx
                  |
suffix            j
```

现在`needle[i] != needle[j]`,将**`i`回溯到`next[i]`**  
> 此处的回溯与计算出`next`数组之后,比较目标串和主串时的回溯,原理是一样的 :  
>```
>      j
> aabaaac
>    aabaaac
>      i
>```
> 失配,已经匹配的部分`aa`存在公共前后缀`a`,因此将`i`赋值为1,`j`保持不变:  
>```
>      j
> aabaaac
>     aabaaac
>      i
>```



将上述计算`next`数组的流程写成代码 :  
```Cpp
/*
 * needle : 目标串
 * next : 返回参数 next[x]表示在x位置失配时,j应该赋值为几
 */
void getNext(std::string& needle, std::vector<int>& next)
{
    /* next的长度显然和needle一样,全体初始化为0 */
    next.clear();
    next.resize(needle.size(), 0);

    int i = 0;
    int j = 1;
    while(j + 1 < needle.size())
    {
        printf("%d %d\n", i, j);

        if(needle[i] == needle[j])
        {
            next[j + 1] = i + 1;
            i++;
            j++;
        }
        else if(i == 0)
        {
            j++;
        }
        else
        {
            i = next[i];
        }
    }
}
```

算出`next`数组之后,进行字符串搜索就很简单了 :  

```Cpp
class Solution {
public:
    int strStr(string haystack, string needle) {
        /* 计算next数组 */    
        std::vector<int> next;
        getNext(needle, next);
        
        /* 搜索 */
        int i = 0;
        int j = 0;
        while(i < haystack.size() && j < needle.size())
        {
            if(haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else if(j == 0)
            {
                i++;
            }
            else
            {
                j = next[j];
            }
        }
        
        /* 返回结果 */
        if(j == needle.size())
            return i - j;
        else
            return -1;
    }
    
    /*
     * needle : 目标串
     * next : 返回参数 next[x]表示在x位置失配时,j应该赋值为几
     */
    void getNext(std::string& needle, std::vector<int>& next)
    {
        /* next的长度显然和needle一样,全体初始化为0 */
        next.clear();
        next.resize(needle.size(), 0);

        int i = 0;
        int j = 1;
        while(j + 1 < needle.size())
        {
            if(needle[i] == needle[j])
            {
                next[j + 1] = i + 1;
                i++;
                j++;
            }
            else if(i == 0)
            {
                j++;
            }
            else
            {
                i = next[i]; // 回溯
            }
        }
    }
};
```

运行结果比较 :  

| 方案     | Runtime | Memeroy |
| :-:      | -:       | -:     |
| 暴力搜索 | 1292 ms | 9.2 MB  |
| KMP     |    4 ms | 9.8 MB  |

Markdown使用 帮助


匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

我有一头小毛驴,我从来也不骑。