c2dbfb89.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;
const int M = 5e6 + 5;

struct AC
{
    static const int CS = 2;
    int node[N][CS], fail[N], nodeCnt = 0;
    i64 sum[N];

    inline void clear()
    {
        ++nodeCnt;
        memset(node, 0, sizeof(int) * CS * (nodeCnt + 1));
        memset(fail, 0, sizeof(int) * nodeCnt);
        memset(sum, 0, sizeof(i64) * nodeCnt);
        nodeCnt = 0;
    }

    inline void insert(const char *str, int len)
    {
        int cur = 0;
        for (int i = 0; i < len; ++i)
        {
            int &next = node[cur][str[i] - '0'];
            if (!next)
            {
                next = ++nodeCnt;
            }
            cur = next;
        }
        sum[cur] = 1LL;
    }

    inline void build()
    {
        queue<int> q;
        for (int i = 0; i < CS; ++i)
        {
            if (node[0][i])
            {
                q.emplace(node[0][i]);
            }
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < CS; ++i)
            {
                int &v = node[u][i];
                if (v)
                {
                    fail[v] = node[fail[u]][i];
                    sum[v] += sum[fail[v]];
                    q.emplace(v);
                }
                else
                {
                    v = node[fail[u]][i];
                }
            }
        }
    }

    inline i64 search(const char *str, int len)
    {
        i64 res = 0LL;
        int cur = 0;
        for (int i = 0; i < len; ++i)
        {
            cur = node[cur][str[i] - '0'];
            res += sum[cur];
        }
        return res;
    }
};

AC small, big;

char str[M], decrypted[M];

inline void decrypt(const char *str, char *dest, int len, int shift)
{
    for (int i = 0; i < len; ++i)
    {
        dest[i] = str[(i + shift) % len];
    }
}

inline void solve()
{
    small.clear();
    big.clear();

    int n;
    read(n);

    vector<vector<char>> vec;

    i64 L = 0;
    size_t split = 0;
    for (int cas = 0, len; cas < n; ++cas)
    {
        scanf("%s", str);
        len = strlen(str) - 1;
        decrypt(str + 1, decrypted, len, L % len);
        if (str[0] == '?')
        {
            L = small.search(decrypted, len) + big.search(decrypted, len);
            printf("%lld\n", L);
        }
        else
        {
            vec.emplace_back(vector<char>(decrypted, decrypted + len));
            if (small.nodeCnt >= 1000)
            {
                small.clear();
                big.clear();
                for (const auto &x : vec)
                {
                    big.insert(x.data(), x.size());
                }
                big.build();
                split = vec.size();
            }
            else
            {
                small.clear();
                for (size_t i = split; i < vec.size(); ++i)
                {
                    small.insert(vec[i].data(), vec[i].size());
                }
                small.build();
            }
        }
    }
}

int main()
{
    int T;
    read(T);

    for (int cas = 1; cas <= T; ++cas)
    {
        printf("Case #%d:\n", cas);
        solve();
    }

    return 0;
}