HW4 p4

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define ll unsigned long long
#define TOTAL 2

ll INF = 18446744073709551610ULL;
ll prime[TOTAL] = {122420729, 1000000009};
ll D[TOTAL]; // d^(M-1) for rolling hash
int table[122420729][TOTAL]; // Hash table
int N, Q, M;
int d = 27;
ll ans = 0;

void helper(char* str, int P){
    ll min_value_0 = INF;
    ll cur_0 = 0;
    ll min_value_1 = INF;
    ll cur_1 = 0;
    // Normal hash
    for(int j=0; j<M; j++){
        cur_0 = (((d*cur_0)%prime[0]) + (str[j]-'a'+1)) % prime[0]; // 1st prime
        cur_1 = (((d*cur_1)%prime[1]) + (str[j]-'a'+1)) % prime[1]; // 2nd prime
    }
    if(cur_0 < min_value_0) min_value_0 = cur_0;
    if(cur_1 < min_value_1) min_value_1 = cur_1;
    // Rotate
    for(int j=1; j<M; j++){
        // 1st prime
        cur_0 = cur_0 + prime[0];
        cur_0 -= (D[0] * (str[j-1]-'a'+1)) % prime[0];
        cur_0 %= prime[0];
        cur_0 *= d;
        cur_0 %= prime[0];
        cur_0 += (str[j-1]-'a'+1);
        cur_0 %= prime[0];
        if(cur_0 < min_value_0) min_value_0 = cur_0;
        // 2nd prime
        cur_1 = cur_1 + prime[1];
        cur_1 -= (D[1] * (str[j-1]-'a'+1)) % prime[1];
        cur_1 %= prime[1];
        cur_1 *= d;
        cur_1 %= prime[1];
        cur_1 += (str[j-1]-'a'+1);
        cur_1 %= prime[1];
        if(cur_1 < min_value_1) min_value_1 = cur_1;
    }
    // Linear Probing
    int loc = min_value_0;
    while(table[loc][0]!=0 && table[loc][1]!=min_value_1){
        loc = (loc+1)%prime[0];
    }
    // Hash the min value and update answer
    if(table[loc][0] == 0){
        if(P==2) return;
        table[loc][0] = 1;
        table[loc][1] = min_value_1;
    }
    else{
        if(P==1){
            ans += table[loc][0];
            table[loc][0] += 1;
        }
        else if(P==2){
            table[loc][0] -= 1;
            ans -= table[loc][0];
        }
    }
}

int main(){
    scanf("%d %d", &N, &Q);
    char str[1000000+5];

    // Preprocess the first str to get D
    scanf("%s", str);
    M = strlen(str);
    for(int i=0; i<TOTAL; i++){
        D[i] = 1;
        for(int j=0; j<M-1; j++){
            D[i] = (D[i]*d)%prime[i];
        }
    }
    helper(str, 1);
    // Stage 1
    for(int i=1; i<N; i++){
        scanf("%s", str);
        helper(str, 1);
    }
    printf("%lld\n", ans);
    // Stage 2
    int P;
    for(int i=0; i<Q; i++){
        scanf("%d", &P);
        scanf("%s", str);
        helper(str, P);
        printf("%lld\n", ans);
    }
    return 0;
}