HackerEarth Yet another problem with Strings solution

YASH PAL,
In this HackerEarth Yet another problem with Strings problem solution You are given a 0-indexed array S with N strings, numbered 0 through N-1, and Q queries to handle. All strings in this problem are nonempty and consist of lowercase English letters.
Let’s create an integer variable LAST_YES to decipher the input. LAST_YES should be equal to the index of the last query that was of the first type and had an answer “YES”. Queries are 0-indexed. LAST_YES is initially equal to zero. Note that LAST_YES can’t be changed in the first query because the first query’s index is zero.
There are two types of queries.
The first type is of ciphered form “1 t”, where t is a string of lowercase English characters. Add LAST_YES to each character in t to get its deciphered value. E.g. the given string cdxyyz with LAST_YES equal to 2 denotes a deciphered string efzaab. You should check whether at least one element of S is a substring of deciphered t. In a single line print “YES” or “NO”.
The second type is of ciphered form “2 i alpha”, where i and alpha are integers.
i (0 ≤ i < |S|) denotes an index in the array S.
alpha (0 ≤ alpha < 26) denotes a single lowercase English letter.
To decipher a query you should add LAST_YES to i and to alpha. In the other words, you can get a deciphered values using the following C++ and Java code:
i = (i + LAST_YES) % N;
alpha = (alpha + LAST_YES) % 26;
After deciphering a query you should add a letter alpha at the end of the i-th string in S.
HackerEarth Yet another problem with Strings problem solution

HackerEarth Yet another problem with Strings problem solution.

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 100, pr = 53, pr2 = 59, pr3 = 14243, bpr = 1e9 + 21, SZ = 1 << 20;

int nxt[N][26];
int add[N], now[N], len[N];
int sz;
bool no_p[N];

int pos[N];

int p[N], p2[N];
vector <pair <pair <int, int>, int> > Map[SZ];
int h[N], h2[N], h_tree[N], h_tree2[N];

inline void Insert (const pair <int, int> &h, const int &x) {
    int pos = (h.first + h.second * 1ll * pr3) % SZ;
    for (auto it : Map[pos])
        if (it.first == h)
            return;
    Map[pos].emplace_back (make_pair (h, x));
}

inline void Delete (const pair <int, int> &h) {
    int pos = (h.first + h.second * 1ll * pr3) % SZ;
    for (int it = 0; it < Map[pos].size (); ++it) {
        if (Map[pos][it].first == h) {
            Map[pos].erase (Map[pos].begin () + it);
            return;
        }
    }           
}

inline int Find (const pair <int, int> &h) {
    int pos = (h.first + h.second * 1ll * pr3) % SZ;
    for (auto it : Map[pos])
        if (it.first == h)
            return it.second;
    return -1;
}

inline int add_s (const string &s) {
    int v = 0;
    for (auto ch : s) {
        if (!nxt[v][ch - 'a'])
            nxt[v][ch - 'a'] = ++sz;
        v = nxt[v][ch - 'a'];
    }
    ++add[v];
    return v;
}

inline int get_hash (const int &h, const int &pw) {
    return (h * 1ll * p[N - 1 - pw]) % bpr;
}

inline int get_hash2 (const int &h, const int &pw) {
    return (h * 1ll * p2[N - 1 - pw]) % bpr;
}

inline void dfs_1 (const int &v, int pref_sum) {
    pref_sum += add[v];
    now[v] = pref_sum;
    add[v] = 0;
    Insert (make_pair (get_hash (h_tree[v], 0), get_hash2 (h_tree2[v], 0)), v);
    for (int ch = 0; ch < 26; ++ch) {
        int to = nxt[v][ch];
        if (!to)
            continue;
        len[to] = len[v] + 1;
        h_tree[to] = (h_tree[v] + ((ch + 1) * 1ll * p[len[v]])) % bpr;
        h_tree2[to] = (h_tree2[v] + ((ch + 1) * 1ll * p2[len[v]])) % bpr;
        dfs_1 (to, pref_sum);
    }
}

inline void dfs_2 (const int &v) {
    if (no_p[v])
        return;
    int x = add[v] + now[v];
    assert (x >= 0);
    if (x > 0)
        return;
    no_p[v] = 1;
    for (int ch = 0; ch < 26; ++ch) {
        int to = nxt[v][ch];
        if (!to)
            continue;
        add[to] += add[v];
        dfs_2 (to);
    }
    add[v] = 0;
}

int main () {

    #ifdef LOCAL
    freopen ("in", "r", stdin);
    freopen ("out", "w", stdout);
    #endif

    ios_base :: sync_with_stdio (0);
    cin.tie (0);

    p[0] = 1;
    p2[0] = 1;

    for (int i = 1; i < N; ++i) {
        p[i] = (p[i - 1] * 1ll * pr) % bpr;
        p2[i] = (p2[i - 1] * 1ll * pr2) % bpr;
    }

    int n, q;
    
    cin >> n >> q;

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        pos[i] = add_s (s);
    }

    dfs_1 (0, 0);
    
    dfs_2 (0);

    int lastq = 0;
    
    string t;
    
    for (int test = 0; test < q; ++test) {
        int q_type;
        cin >> q_type;
        if (q_type == 1) {
            cin >> t;
            h[0] = (t[0] - 'a' + 1);
            h2[0] = (t[0] - 'a' + 1);
            bool ans = 0;
            for (int i = 1; i < t.size (); ++i) {
                h[i] = (h[i - 1] + ((t[i] - 'a' + 1) * 1ll * p[i])) % bpr;
                h2[i] = (h2[i - 1] + ((t[i] - 'a' + 1) * 1ll * p2[i])) % bpr;
            }           

            for (int i = t.size () - 1; i >= 0; --i) {
                int l = i, r = t.size ();
                while (r - l > 1) {
                    int mid = (r + l) >> 1;
                    auto g = make_pair ((h[mid] - h[i] + bpr) % bpr, (h2[mid] - h2[i] + bpr) % bpr);
                    g.first = get_hash (g.first, i + 1);
                    g.second = get_hash2 (g.second, i + 1);
                    if (Find (g) == -1)
                        r = mid;
                    else
                        l = mid;
                }
                auto g = make_pair ((h[l] - h[i] + bpr) % bpr, (h2[l] - h2[i] + bpr) % bpr);
                g.first = get_hash (g.first, i + 1);
                g.second = get_hash2 (g.second, i + 1);
                int v = Find (g);
                ans |= (!no_p[v]);
            }

            int l = -1, r = t.size ();
            while (r - l > 1) {
                int mid = (r + l) >> 1;
                auto g = make_pair (h[mid], h2[mid]);
                g.first = get_hash (g.first, 0);
                g.second = get_hash2 (g.second, 0);
                if (Find (g) == -1)
                    r = mid;
                else
                    l = mid;
            }
            if (l > -1) {
                auto g = make_pair (h[l], h2[l]);
                g.first = get_hash (g.first, 0);
                g.second = get_hash2 (g.second, 0);
                int v = Find (g);
                ans |= (!no_p[v]);
            }
            cout << (ans ? "YESn" : "NOn");
            if (ans)
                lastq = test;
        } else {
            int j, alpha;
            cin >> j >> alpha;
            j = (j + lastq) % n;
            alpha = (alpha + lastq) % 26;
            int v = pos[j];
            if (!nxt[v][alpha]) {
                nxt[v][alpha] = ++sz;
                now[sz] = now[v];
                len[sz] = len[v] + 1;
                h_tree[sz] = (h_tree[v] + ((alpha + 1) * 1ll * p[len[v]])) % bpr;
                h_tree2[sz] = (h_tree2[v] + ((alpha + 1) * 1ll * p2[len[v]])) % bpr;
                Insert (make_pair (get_hash (h_tree[sz], 0), get_hash2 (h_tree2[sz], 0)), sz);
            }
            --add[v];
            ++add[nxt[v][alpha]];
            dfs_2 (v);
            pos[j] = nxt[v][alpha];
        }
    }
    
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mp make_pair
#define pb push_back
typedef long long ll;
const int inf = 1e9 + 5;
const int nax = 1e6 + 15;

vector<pair<int,int> > H = vector<pair<int,int> > {
    make_pair(27, 1000*1000*1000 + 7),
    //make_pair(61, 1000*1000*1000 + 9),
    make_pair(101,1000*1000*1001 + 27)
};
const int K = H.size();
const vector<int> HASH_ZERO = vector<int>(K, 0);
vector<int> powers[nax];
void initPowers() {
    powers[0] = vector<int>{1, 1, 1};
    RI(i, nax-1) {
        REP(j, K) {
            ll tmp = (ll) powers[i-1][j] * H[j].first;
            powers[i].pb(int(tmp % H[j].second));
        }
    }
}
vector<int> mul(vector<int> w, int len) {
    REP(i, K) w[i] = (ll) w[i] * powers[nax-1-len][i] % H[i].second;
    return w;
}
vector<int> sub(vector<int> a, vector<int> b) {
    REP(i, K) a[i] = (a[i] - b[i] + H[i].second) % H[i].second;
    return a;
}

vector<int> extendHash(vector<int> w, int ch) {
    for(int i = 0; i < K; ++i) {
        ll tmp = (ll) w[i] * H[i].first + ch + 1;
        w[i] = tmp % H[i].second;
    }
    return w;
}

struct Node {
    int endHere = 0;
    int sum = 0; // sum over endHere of ansectors, including me
    vector<int> hash;
} node[nax];

map<vector<int>, int> mapHash; // not hashmap ;p
int COUNTER, LAST_Q;
int trie[nax][26];
char sl[nax];
int where[nax]; // initially 0 for all N strings

void update(int a) {
    REP(i, 26) {
        int b = trie[a][i];
        if(b == 0) continue;
        bool before = (bool) node[b].sum;
        node[b].sum = node[a].sum + node[b].endHere;
        if(before != (bool) node[b].sum)
            update(b);
    }
}

int len[nax];
void addLetter(int id, int ch) {
    ++len[id];
    int v = where[id];
    int & child = trie[v][ch];
    if(!child) {
        child = ++COUNTER;
        node[child].hash = extendHash(node[v].hash, ch);
        mapHash[mul(node[child].hash, len[id])] = child;
    }
    where[id] = child;
    node[v].endHere--;
    node[v].sum--;
    node[child].endHere++;
    update(v);
}

void queryAdd(int n) {
    int i, j;
    scanf("%d%d", &i, &j);
    assert(0 <= i && 0 <= j && i < n && j < 26);
    addLetter((i + LAST_Q) % n, (j + LAST_Q) % 26);
}

vector<int> t[nax];
bool queryCheck() {
    static ll total = 0;
    scanf("%s", sl);
    int d = strlen(sl);
    total += d;
    assert(total <= 500 * 1000);
    for(int i = 0; i < d; ++i)
        assert('a' <= sl[i] && sl[i] <= 'z');
    for (int i = 0; i < d; ++i)
        sl[i] = 'a' + ((sl[i] - 'a' + LAST_Q) % 26);
    t[0] = HASH_ZERO;
    FOR(i,1,d) t[i] = extendHash(t[i-1], sl[i-1] - 'a');
    REP(i, d) {
        int low = i - 1, high = d - 1;
        while(low < high) {
            int j = (low + high + 1) / 2;
            vector<int> interval = sub(mul(t[j+1], j+1), mul(t[i], i));
            interval = mul(interval, nax-1 - i);
            auto it = mapHash.find(interval);
            if(it == mapHash.end()) high = j -1;
            else {
                low = j;
                if(node[(*it).second].endHere) return true;
            }
        }
    }
    return false;
}

int main() {
    initPowers();
    int n, q;
    scanf("%d%d", &n, &q);
    assert(1 <= min(n, q) && max(n, q) <= 500 * 1000);
    node[0].endHere = node[0].sum = n;
    node[0].hash = HASH_ZERO;
    ll total = 0;
    REP(id, n) {
        scanf("%s", sl);
        int d = strlen(sl);
        total += d;
        REP(j, d) assert('a' <= sl[j] && sl[j] <= 'z');
        REP(j, d) addLetter(id, sl[j] - 'a');
    }
    assert(total <= 500 * 1000);
    REP(i, q) {
        int which;
        scanf("%d", &which);
        assert(1 <= which && which <= 2);
        if(which == 1) {
            bool ans = queryCheck();
            puts(ans ? "YES" : "NO");
            if(ans) LAST_Q = i;
        }
        else queryAdd(n);
    }
    return 0;
}
coding problems solutions