题目
看什么字串是其他字串的子字串
思路
字典树插入后缀时val++
查询时如果val>1就代表有其他字的子字串是他
这个做法如果我可以O1插入后缀的话应该会比较快
但是后缀树的那个算法我不会
所以算了
```cpp
class TrieTree {
TrieTree* child[128];
public:
int val;
TrieTree(): val(0), child{0} { }
TrieTree* get(char c) {
if(!child[c]) child[c] = new TrieTree();
return child[c];
}
TrieTree* get(const string& s) {
TrieTree* t = this;
for(char c: s) {
t = t->get(c);
t->val ++;
}
return t;
}
TrieTree* find(char c) {
return child[c];
}
TrieTree* find(const string& s) {
TrieTree* t = this;
for(char c: s) {
t = t->find(c);
if(!t) break;
}
return t;
}
};
class Solution {
public:
vector<string> stringMatching(vector<string>& words)
{
TrieTree *save = new TrieTree();
int n = words.size();
vector<string> res;
for(int i = n-1 ; i >= 0 ; i