前言

$scanf$ 只能过 $90\%$，但是 $cin$ 可以过 $100\%$，不知道是不是数据的问题。

不过这题是个挺好的字典树的题。

C、联想标语

思路

很容易想到把给定的字符串插到字典树上面去，但是查询是要去除一些字符串的前缀的。

那么在字典树上匹配的串，就必须完全匹配这个前缀，所以考虑怎么在树上打标记。

其实很简单，在插入字符串的时候，给最后一次 lenovo 出现的位置，一直到串末尾，都让标记 + 1 即可。

查询的时候，走到匹配的串的末尾，末尾节点的值，就是需要去除掉的答案。

struct TrieNode {
    string ch;
    bool isEnding;
    int hasLenovo;
    unordered_map<char, TrieNode*> children;

    TrieNode(string c) : ch(c), isEnding(false), hasLenovo(0) {}
};

TrieNode* NewTrieNode(string charStr) {
    return new TrieNode(charStr);
}

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = NewTrieNode("/");
    }

    void Insert(string word, int pos) {
        TrieNode* node = root;
        for (int i = 0; i < word.length(); ++i) {
            char code = word[i];
            if (node->children.find(code) == node->children.end()) {
                TrieNode* value = NewTrieNode(string(1, code));
                node->children[code] = value;
            }
            if (i >= pos) {
                node->children[code]->hasLenovo++;
            }
            node = node->children[code];
        }
        node->isEnding = true;
    }

    pair<bool, int> Find(string word) {
        TrieNode* node = root;
        int ans = 0;
        for (int i = 0; i < word.length(); ++i) {
            char code = word[i];
            if (node->children.find(code) == node->children.end()) {
                return make_pair(false, 0);
            }
            if (i == word.length() - 1) {
                ans += node->children[code]->hasLenovo;
            }
            node = node->children[code];
        }
        return make_pair(true, ans);
    }
};

void solve() {
    int n;
    cin >> n;
    Trie trie;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int op;
        cin >> op;
        string s;
        cin >> s;
        int m = s.length();
        if (op == 1) {
            int pos = 1e18;
            for (int j = 0; j < m; ++j) {
                if (s.substr(j, min(m - j, 6)) == "lenovo") {
                    pos = j;
                }
            }
            if (pos < m) {
                ans++;
            }
            trie.Insert(s, pos);
        } else {
            pair<bool, int> result = trie.Find(s);
            cout << ans - result.second << endl;
        }
    }
}