Re: [閒聊] 每日leetcode

[dont (dont)]

1408. String Matching in an Array

## 思路

字串兩兩做KMP檢查 不過測資用暴力解反而比較快= =

O(N^2 * k)
N = word個數
k = word最大長度

## Code

```cpp
class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        vector<string> res;
        int n = words.size();

        for (int i=0; i<n; ++i) {
            vector<int> lps = compute(words[i]);
            for (int j=0; j<n; ++j) {
                if (i == j) continue;
                if (check(words[j], words[i], lps)) {
                    res.push_back(words[i]);
                    break;
                }
            }
        }
        return res;
    }

private:
    vector<int> compute(string& pattern) {
        int n = pattern.size();
        vector<int> lps(n, 0);

        int j = 0;
        for (int i=1; i<n; ++i) {
            while (j && pattern[i] != pattern[j])
                j = lps[j-1];
            if (pattern[i] == pattern[j]) {
                lps[i] = ++j;
            }
        }
        return lps;
    }

    bool check(string& str, string& pattern, vector<int> lps) {
        int len_s = str.size();
        int len_p = pattern.size();

        int j = 0;
        for (int i=0; i<len_s; ++i) {
            while (j && str[i] != pattern[j])
                j = lps[j-1];
            if (str[i] == pattern[j]) {
                ++j;
            }
            if (j == len_p)
                return true;
        }
        return false;
    }
};
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 93.118.42.62 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736252625.A.FF3.html
推 sustainer123: kmp忘光光了 哇哇嗚嗚嗚
推 DJYOMIYAHINA: 大師==