Implement strStr

LeetCode笔记 阅读(61)

编号 : 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使用 帮助