Soluție HackerRank pentru Randomness, subdomeniul Probability, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Randomness
  • Domeniu: Probability
  • Limbaj: C++14

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

Cerință

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 ≤ N ≤ 75000
4 ≤ Q ≤ 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 sursă

//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;
}
HackerRank Probability – Randomness