题解 | #接头密匙#

class Solution {
private:
    int son[100010][10], idx;
    int ed[100010], st[100010];
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param b int整型vector<vector<>> 
     * @param a int整型vector<vector<>> 
     * @return int整型vector
     */
    void insert(vector<int>& s)
    {
        int p = 0;
        int len = s.size();
        for (int i = 0; i + 1 < len; i ++ )
        {
            int x = s[i + 1] - s[i]; // 差分插入 Trie 树
            if (!son[p][x]) son[p][x] = ++ idx; // 创建子节点
            p = son[p][x];
            st[p] ++; // 记录经过当前p节点的字符串数量
        }
        ed[p] ++; // 记录以p为叶子节点的字符串的数量
    }

    int query(vector<int>& s)
    {
        int p = 0;
        int len = s.size();
        for (int i = 0; i + 1 < len; i ++ )
        {
            int x = s[i + 1] - s[i];
            if (!son[p][x]) return 0;
            p = son[p][x];
        }
        return st[p];
    }

    vector<int> countConsistentKeys(vector<vector<int> >& b, vector<vector<int> >& a) {
        // write code here
        vector<int> ans;
        int m = b.size(), n = a.size();
        for (int i = 0; i < n; i ++ )
            insert(a[i]); // 插入a的每个串
        for (int i = 0; i < m; i ++ )
            ans.push_back(query(b[i])); // 查询b的每个串
        return ans;
    }
};