28. Implement strStr()

题目

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: 2Example 2:Input: haystack = "aaaaa", needle = "bba"Output: -1

解析

• kmp算法

class Solution_28 {public:    // find_first_of()在源串中从位置pos起往后查找，只要在源串中遇到一个字符，该字符与目标串中任意一个字符相同，就停止查找，返回该字符在源串中的位置；若匹配失败，返回npos。    // string查找find()函数，都有唯一的返回类型，那就是size_type，即一个无符号整数（按打印出来的算）。若查找成功，返回按查找规则找到的第一个字符或子串的位置；若查找失败，返回npos，即-1（打印出来为4294967295）    int strStr(string haystack, string needle) { // 字符串匹配        int ret = haystack.find(needle);        return ret;    }    char *strStr1(char *haystack, char *needle) {        int len1 = strlen(haystack);        int len2 = strlen(needle);        if (len1 < len2)        {            return NULL;        }        if (len2 == 0)        {            return haystack;        }        int i = 0;        for (; i < len1 - len2 + 1; i++)        {            int j = 0;            while (haystack[i+j]==needle[j])            {                if (j == len2 - 1)                {                    return haystack + i;                }                j++;            }        }        return NULL;    }    void getNextval(char*p,vector
    
     & next)    {        int len = strlen(p);        next[0] = -1;        int k = -1; //前缀序列        int j = 0;        while (j < len)        {            if (k==-1||p[j]==p[k])            {                j++; k++;                if (p[j]!=p[k])                {                    next[j] = k;                }                else                {                    next[j] = next[k];                }            }            else            {                k = next[k];            }        }    }    char *strStr(char *haystack, char *needle)    {        int len1 = strlen(haystack);        int len2 = strlen(needle);        int i = 0, j = 0;        vector
     
       next(128,0);        getNextval(needle, next);        while (i
      
     
    

题目来源