HackerRank Probability – Randomness

Challenge: Randomness

Subdomeniu: Probability (probability)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736458

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/randomness/problem

Cerinta

You're given a string $S$ of $N$ characters. It's known that the string consists of lowercase Latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {'a', 'b', ..., 'z'}. All the letters have equal probability to appear.

You're given $Q$ queries on this string. Each query is of the form `P C`, where $P$ is an integer between $1$ and $N$ (both inclusive) and $C$ is a character from the set {'a', 'b', ..., 'z'}. Both $P$ and $C$ were chosen at random and independently from other queries. 

When you have a query of the form `P C` you have to change the $P$<sup>$th$</sup> symbol of $S$ to $C$. After every change we ask you to output the number of distinct nonempty sub-strings of $S$.

Input Format

The first line of input consists of two single space-separated integers $N$ and $Q$, the length of the string $S$ and the number of queries, respectively.

The second line contains string $S$.

The following $Q$ lines describe the queries in the form `P C`, where $P$ and $C$ are also separated with a single space.

**Constraints**  
$4 \le N \le 75000$  
$4 \le Q \le 75000$

Output Format

Output $Q$ lines. Output the number of distinct substrings of $S$ after the $i$<sup>$th$</sup> query on the $i$<sup>$th$</sup> line of the output.

Cod sursa

//randomness.cpp
//Randomness
//Daily Challenges - Week 1
//Author: derekhh

#include<cstdio>
#include<cstring>
using namespace std;

char s[75001];
const int MOD = 1000003;
const int BASE = 27;

struct Node {
	long long str;
	int cnt;
	Node* next;
};

Node* hash[MOD];

long long ans;

int n;
long long pow[10];

void modify(long long val, int delta)
{
	int mod = val % MOD;
	Node* cur = hash[mod];
	Node* tmp = NULL;

	bool newStr = true;
	while (cur != NULL)
	{
		if (cur->str == val)
		{
			cur->cnt += delta;
			if (cur->cnt == 0)
			{
				ans--;
				if (tmp == NULL)
					hash[mod] = hash[mod]->next;
				else
					tmp->next = cur->next;
			}
			return;
		}
		tmp = cur;
		cur = cur->next;
	}

	Node* node = new Node;
	node->str = val;
	node->cnt = delta;
	ans += delta;
	node->next = hash[mod];
	hash[mod] = node;
}

void init()
{
	for (int i = 0; i < MOD; i++)
		hash[i] = NULL;
	
	for (int i = 0; i < n; i++)
	{
		long long val = 0;
		for (int len = 1; len <= 9; len++)
		{
			if (i + len - 1 >= n) break;
			val = val * BASE + s[i + len - 1] - 'a' + 1;
			modify(val, 1);
		}
	}
}

void update(int p, char ch)
{
	for (int i = p - 8; i <= p; i++)
	{
		long long val = 0;
		for (int len = 1; len <= 9; len++)
		{
			if (i + len - 1 < 0 || i + len - 1 >= n) break;
			val = val * BASE + s[i + len - 1] - 'a' + 1;
			if (i + len - 1 >= p)
				modify(val, -1);
		}
	}
	s[p] = ch;
	for (int i = p - 8; i <= p; i++)
	{
		long long val = 0;
		for (int len = 1; len <= 9; len++)
		{
			if (i + len - 1 < 0 || i + len - 1 >= n) break;
			val = val * BASE + s[i + len - 1] - 'a' + 1;
			if (i + len - 1 >= p)
				modify(val, 1);
		}
	}
}

int main()
{
	int q;
	scanf("%d %d", &n, &q); getchar();
	scanf("%s", s);
	init();
	for (int i = 10; i <= n; i++)
		ans += n - i + 1;
	while (q--)
	{
		int p; char ch;
		scanf("%d %c", &p, &ch); getchar();
		update(p - 1, ch);
		printf("%lld\n", ans);
	}
	return 0;
}