題目描述：有兩個(gè)字符串s和s1,尋找s子串在s1中第一次出現(xiàn)的位置，如果沒有則返回-1，若s1為空，則返回0.

我自己的解法

循環(huán)遍歷字符串s，當(dāng)s[i] == s1[0]，即第一個(gè)字符相等時(shí)，就在來一輪循環(huán)，按個(gè)比較每個(gè)字符是否相等，若相等則返回i - s1.size()，若不相等，則回退i到i - j.

image.png

• 當(dāng)整個(gè)字符串匹配成功時(shí)，我們有右邊的i，因?yàn)橐还财ヅ淞?code>s1.size()次，所以想要求到開始的索引，只需減去s1.size()

• 當(dāng)只匹配了一部分時(shí)，有圖不難看出，將i回退到i - j即可

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (needle == "")
        {
            return 0;
        }
        int i = 0;
        int j;
        bool is_substr = true;
        while (i < haystack.length())
        {
            if (haystack[i] == needle[0])
            {
                for (j = 0; j < needle.size(); j++, i++)
                {
                    if (needle[j] != haystack[i])
                    {
                        is_substr = false;
                        break;
                    }
                }
                if (is_substr)
                {
                    return i - needle.size();
                }
                else
                {
                    is_substr = true;
                    i = i - j;
                }
            }
            i++;
        }
        return -1;
    }
};

image.png

宮水三葉的題解 （KMP算法）

原鏈接,可以自己去看一下，寫的真的很好。膜大佬orz

文章關(guān)于KMP算法已經(jīng)是說的比較清楚了，我下面單純補(bǔ)充幾點(diǎn)我當(dāng)時(shí)的困擾

1. 前綴和后綴
   前綴和后綴是不包括整個(gè)單詞的，例如單詞read, r, re,rea都是前綴，但是read就不能算前綴，后綴也是同理

2. 為什么需要兩個(gè)指針j ，i
   j指向已經(jīng)匹配成功字符串的末尾，i用于遍歷匹配串，指向下一個(gè)要匹配的字符

3.next數(shù)組里的數(shù)字到底是什么意思
next[i]里的數(shù)字是指當(dāng)在第i個(gè)字符匹配失敗時(shí)，此時(shí)的最大的相同前后綴的長(zhǎng)度。

4. next函數(shù)的編程實(shí)現(xiàn)
   圖片用的是宮水三葉題解里的圖，我對(duì)這些圖做一些解釋
   
   image.png

next[0] = 0, 因?yàn)樵?號(hào)位置失敗的話，前后綴長(zhǎng)度為0
當(dāng)p[i] == p[j]時(shí)，即兩個(gè)字符匹配成功時(shí)，此時(shí)相同前后綴長(zhǎng)度就可以加一，此時(shí)的j指向是最長(zhǎng)前綴的末尾，所以next[i] = j + 1

image.png

當(dāng)p[i]和p[j]不相等的時(shí)候，按照KMP算法，我們就要回退，因?yàn)榧恿艘粋€(gè)字符就不相等了，所以我們稍微放寬一點(diǎn)要求，匹配不了長(zhǎng)度為j的一整個(gè)字符串，可能可以匹配 j個(gè)字符的開頭的一部分，所以我們?cè)囋噉ext[j - 1],本質(zhì)上是試試公共前綴的公共前綴行不行，不行就在回退，直到匹配上了，或是j變成了0，無法再匹配。

ps:如果對(duì)于j = next[j - 1]不明白看這篇，要是還看不懂，那就多看幾遍吧.

// KMP
class Solution1
{
public:
    int strStr(string s, string p)
    {
        int n = s.size(), m = p.size();
        if (m == 0)
            return 0;
        //設(shè)置哨兵
        s.insert(s.begin(), ' ');
        p.insert(p.begin(), ' ');
        vector<int> next(m + 1);
        //預(yù)處理next數(shù)組
        for (int i = 2, j = 0; i <= m; i++)
        {
            while (j and p[i] != p[j + 1])
                j = next[j];
            if (p[i] == p[j + 1])
                j++;
            next[i] = j;
        }
        //匹配過程
        for (int i = 1, j = 0; i <= n; i++)
        {
            while (j and s[i] != p[j + 1])
                j = next[j];
            if (s[i] == p[j + 1])
                j++;
            if (j == m)
                return i - m;
        }
        return -1;
    }
};

image.png