Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
1
Indexable
Never
#include <unordered_set>
#define MAX_STRING 11001
#define MAX_LENGTH 10

using namespace std;

struct Strings{
	int parent;
	int deathTime;

} strings[MAX_STRING];

unordered_set<int> check[11];

int subStr[26][26][26];
int index;

void init(int N)
{
	for(int i = 0; i < 26; i++)
		for(int j = 0; j < 26; j++)
			for(int k = 0; k < 26; k++)
				subStr[i][j][k] = -1;

	for(int i =0; i < 11; i++)
		check[i].clear();

	index = 0;
}

int findParent(int u)
{
	if(u == strings[u].parent)
		return u;
	strings[u].parent = findParent(strings[u].parent);
	return strings[u].parent;
}

int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[])
{
	int idStr = index;
	Strings str;
	str.parent = idStr;
	str.deathTime = mTimestamp + mLifespan;
	strings[idStr] = str;

	for(int i = 0; i < mLen - 2; i++){
		int a = mStr[i] - 'a';
		int b = mStr[i+1] - 'a';
		int c = mStr[i+2] - 'a';

		if(subStr[a][b][c] != -1){
			int idP = findParent(subStr[a][b][c]);
			if(strings[idP].deathTime > mTimestamp){
				strings[idP].parent = idStr;
			}
		}
		subStr[a][b][c] = idStr;
	}


	check[mLen].insert(idStr);

	for (auto it = check[mLen].begin(); it != check[mLen].end();)
	{
		int idx = *it;
		int p = findParent(idx);
		if (strings[p].deathTime <= mTimestamp) {
			check[mLen].erase(it++);
		}
		else
			it++;
	}

	index++;

	return check[mLen].size();
}

int checkString(int mTimestamp, int mLen)
{
	for (auto it = check[mLen].begin(); it != check[mLen].end(); )
	{
		int idx = *it;
		int p = findParent(idx);
		if (strings[p].deathTime <= mTimestamp) {
			check[mLen].erase(it++);
			
		}
		else it++;
	}

	return check[mLen].size();

}