代碼随想錄算法訓練營第九天 | 28. 找出字元串中第一個比對項的下标(KMP) 459. 重複的子字元串

代碼随想錄算法訓練營第九天

• • LeetCode28. 找出字元串中第一個比對項的下标(KMP)
  • • 自己實作
    • 題解
    • 總結
  • LeetCode459. 重複的子字元串
  • • 題解
    • 總結

LeetCode28. 找出字元串中第一個比對項的下标(KMP)

題目連結

視訊講解

自己實作

// 暴力法
class Solution {
public:
    int strStr(string haystack, string needle) {
        bool flag = false;
        int i = 0, j = 0;
        for(int i = 0; i < haystack.size(); i++) {
            int j = 0;
            for(; j < needle.size(); j++) {
                if(haystack[i + j] != needle[j]) break;
            }
            if(j == needle.size()) return i;
        }
        return -1;
    }
};
           

題解

// KMP
class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> next = getNext(needle);
        int j = 0;
        for(int i = 0; i < haystack.size(); i++) {

            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }

            if(haystack[i] == needle[j]) j++;

            if(j == needle.size()) return i - j + 1;
        }
        return -1;
    }

    vector<int> getNext(string needle) {
        // 1. 初始化
        // i 表示字尾最後一位，j 表示字首最後一位
        vector<int> next(needle.size(), 0);
        int j = 0;
        // i 從 1 開始 才能進行比較 aabaabaaf 從aa開始
        for(int i = 1; i <  needle.size(); i++) {
            // 前字尾最後一個字母不相同 注意這裡是while，查找前一個位置
            while(j > 0 && needle[i] != needle[j]) j = next[j - 1];
            // 先字尾最後一個字母相同
            if(needle[i] == needle[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
};
           

總結

LeetCode459. 重複的子字元串

題目連結

視訊講解

題解

// 移動比對
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;

        t.erase(t.begin());
        t.erase(t.end() - 1);

        if(t.find(s) == -1) return false;
        return true;
    }
};

// KMP
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        
        vector<int> next = getnext(s);

        int len = s.size();
        // 如果可以被整除則為true 去掉最後一個為0的情況
        if(next[len - 1] != 0 && len % (len - next[len - 1]) == 0) return true;
        return false;
    }

    vector<int> getnext(string s) {
        // 1.初始化
        vector<int> next(s.size(), 0);
        // j 代表字首，i代表字尾
        int j = 0;
        for(int i = 1; i < s.size(); i++) {

            while(j > 0 && s[i] != s[j]) j = next[j - 1];

            if(s[i] == s[j]) j++;

            next[i] = j;
        }
        return next;

    }
};
           

總結