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;
}
};
```