<snippet>
    <content><![CDATA[
template<size_t siz> 
class AutoKmp {
public:
    std::vector<int> pre_same;
    std::vector<std::array<int, siz>> f;
    inline int get(char x) {
        if (x <= '9') return x - '0' + 52;
        if (x <= 'Z') return x - 'A' + 26;
        return x - 'a';
    }
    // f[i][j] 表示在节点i,下一个要匹配j的话 需要去的节点
    AutoKmp(std::string& s, int n = -1) {
        if (n == -1) n = s.size();
        pre_same = {0};
        f.push_back(std::array<int, siz>{});
        pre_same.reserve(n + 10);
        f.reserve(n + 10);
        f[0][get(s[0])] = 1;
        for (int i = 1; i < s.size(); i++) {
            add(s[i]);
        }
    };
    void add(char x) {
        int j = get(x);
        f.emplace_back(std::array<int, siz>{});
        pre_same.push_back(f[pre_same[f.size() - 2]][j]);
        f.back() = f[pre_same[f.size() - 2]];
        f.back()[j] = f.size();
    }
    void pop() {
        pre_same.pop_back();
        f.pop_back();
    }
};
]]></content>
    <!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
    <!-- <tabTrigger>hello</tabTrigger> -->
    <!-- Optional: Set a scope to limit where the snippet will trigger -->
    <!-- <scope>source.python</scope> -->
</snippet>