• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Friday, January 27, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

How Many Substrings? – HackerRank Solution

How Many Substrings?- HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

bhautik bhalala by bhautik bhalala
May 25, 2022
Reading Time: 1 min read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

Table of Contents

  • How Many Substrings? – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
  • Solutions of Algorithms Data Structures Hard HackerRank:
    • Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
  • C++ How Many Substrings? HackerRank Solution
  • Java How Many Substrings? HackerRank Solution
    • Leave a comment below
      • Related posts:

How Many Substrings? – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Solutions of Algorithms Data Structures Hard HackerRank:

Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

C++ How Many Substrings? HackerRank Solution


Copy Code Copied Use a different Browser

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <array>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

#ifdef MYDEBUG
const int dbg = MYDEBUG;
#else
const int dbg = 0;
#endif

struct LogStream {
	LogStream(int line) {
		cerr << "L" << line;
	}

	~LogStream() {
		cerr << endl;
		if (dbg > 0) std::abort();
		for (;;) new int[1 << 25];
	}
};
template<typename T>
const LogStream& operator<<(const LogStream& a, const T& b) {
	cerr << b;
	return a;
}
const LogStream& operator<<(const LogStream& a, ostream& (*b)(ostream&)) {
	cerr << b;
	return a;
}

#define check(cond) if (cond) ; else (LogStream(__LINE__) << "Failed " << #cond << ". ")
#define check_eq(exp, act) check((exp) == (act)) << " expect " << (exp) << ", got " << (act)

#ifdef MYDEBUG
#define dcheck(cond) check(cond)
#else
#define dcheck(cond) check(true)
#endif

typedef long long ll;
#define loop(i, b, e) for (auto i = (b); i < (e); ++i)

template<typename C> void Sort(C& c) { sort(c.begin(), c.end()); }
template<typename C> void Uniq(C& c) { c.erase(unique(c.begin(), c.end()), c.end()); }
template<typename C> void SortAndUniq(C& c) { Sort(c); Uniq(c); }

struct PerNodeData;
string RenderPerNodeData(const PerNodeData&);

// Borrowed code from http://yeda.cs.technion.ac.il/~yona/suffix_tree/

/******************************************************************************
Suffix Tree Version 2.1
by:		 Dotan Tsadok.
Instructor: Mr. Shlomo Yona.
University of Haifa, Israel.
December 2002.

Current maintainer:
	Shlomo Yona	<shlomo@cs.haifa.ac.il>

DESCRIPTION OF THIS FILE:
This is the decleration file suffix_tree.h and it contains declarations of the
interface functions for constructing, searching and deleting a suffix tree, and
to data structures for describing the tree.

COPYRIGHT
Copyright 2002-2003 Shlomo Yona

LICENSE
This library is free software; you can redistribute it and/or modify it
under the same terms as Perl itself.
*******************************************************************************/

/* A type definition for a 32 bits variable - a double word. */
#define	 DBL_WORD	  unsigned long   

/* Error return value for some functions. Initialized  in ST_CreateTree. */
DBL_WORD	ST_ERROR;

/******************************************************************************/
/*						   DATA STRUCTURES								  */
/******************************************************************************/
/* This structure describes a node and its incoming edge */
typedef struct SUFFIXTREENODE
{
   /* A linked list of sons of that node */
   struct SUFFIXTREENODE*   sons;
   /* A linked list of right siblings of that node */
   struct SUFFIXTREENODE*   right_sibling;
   /* A linked list of left siblings of that node */
   struct SUFFIXTREENODE*   left_sibling;
   /* A pointer to that node's father */
   struct SUFFIXTREENODE*   father;
   /* A pointer to the node that represents the largest 
   suffix of the current node */
   struct SUFFIXTREENODE*   suffix_link;
   /* Index of the start position of the node's path */
   DBL_WORD				 path_position;
   /* Start index of the incoming edge */
   DBL_WORD				 edge_label_start;
   /* End index of the incoming edge */
   DBL_WORD				 edge_label_end;
   
   // CUSTOM DATA NOT BELONGING TO THE ORIGINAL SUFFIX TREE LIBRARY.
   PerNodeData* more_data;
} NODE;

/* This structure describes a suffix tree */
typedef struct SUFFIXTREE
{
   /* The virtual end of all leaves */
   DBL_WORD				 e;
   /* The one and only real source string of the tree. All edge-labels
	  contain only indices to this string and do not contain the characters
	  themselves */
   char*		   tree_string;
   /* The length of the source string */
   DBL_WORD				 length;
   /* The node that is the head of all others. It has no siblings nor a
	  father */
   NODE*					root;
} SUFFIX_TREE;


/******************************************************************************/
/*						 INTERFACE FUNCTIONS								*/
/******************************************************************************/
/* 
   ST_CreateTree :
   Allocates memory for the tree and starts Ukkonen's construction algorithm by
   calling SPA n times, where n is the length of the source string.

   Input : The source string and its length. The string is a sequence of
		   characters (maximum of 256 different symbols) and not
		   null-terminated. The only symbol that must not appear in the string
		   is $ (the dollar sign). It is used as a unique symbol by the
		   algorithm and is appended automatically at the end of the string (by
		   the program, not by the user!). The meaning of the $ sign is
		   connected to the implicit/explicit suffix tree transformation,
		   detailed in Ukkonen's algorithm.

   Output: A pointer to the newly created tree. Keep this pointer in order to
		   perform operations like search and delete on that tree. Obviously,
		   no de-allocating of the tree space could be done if this pointer is
		   lost, as the tree is allocated dynamically on the heap.
*/

SUFFIX_TREE* ST_CreateTree(const char*   str, DBL_WORD length);

/******************************************************************************/
/*
   ST_FindSubstring :
   Traces for a string in the tree. This function is used for substring search
   after tree construction is done. It simply traverses down the tree starting
   from the root until either the searched string is fully found ot one
   non-matching character is found. In this function skipping is not enabled
   because we don't know wether the string is in the tree or not (see function
   trace_string above).

   Input : The tree, the string W, and the length of W.

   Output: If the substring is found - returns the index of the starting
		   position of the substring in the tree source string. If the substring
		   is not found - returns ST_ERROR.
*/

DBL_WORD ST_FindSubstring(SUFFIX_TREE*	  tree,   /* The suffix array */
						  char*	W,	  /* The substring to find */
						  DBL_WORD		  P);	 /* The length of W */

/******************************************************************************/
/*
   ST_PrintTree :
   This function prints the tree. It simply starts the recoursive function
   ST_PrintNode from the root

   Input : The tree to be printed.
  
   Output: A print out of the tree to the screen.
*/

void ST_PrintTree(SUFFIX_TREE* tree);

/******************************************************************************/
/*
   ST_DeleteTree
   Deletes a whole suffix tree by starting a recoursive call to ST_DeleteSubTree
   from the root. After all of the nodes have been deleted, the function deletes
   the structure that represents the tree.

   Input : The tree to be deleted.

   Output: None.
*/

void ST_DeleteTree(SUFFIX_TREE* tree);

/******************************************************************************/
/*
   ST_SelfTest
   Self test of the tree - search for all substrings of the main string. See
   testing paragraph in the readme.txt file.

   Input : The tree to test.

   Output: 1 for success and 0 for failure. Prints a result message to the
		   screen.
*/

DBL_WORD ST_SelfTest(SUFFIX_TREE* tree);

/******************************************************************************
Suffix Tree Version 2.1

AUTHORS

Dotan Tsadok
Instructor: Mr. Shlomo Yona, University of Haifa, Israel. December 2002.
Current maintainer: Shlomo Yona	<shlomo@cs.haifa.ac.il>

COPYRIGHT

Copyright 2002-2003 Shlomo Yona

LICENSE

This library is free software; you can redistribute it and/or modify it
under the same terms as Perl itself.


DESCRIPTION OF THIS FILE:

This is the implementation file suffix_tree.c implementing the header file
suffix_tree.h.

This code is an Open Source implementation of Ukkonen's algorithm for
constructing a suffix tree over a string in time and space complexity
O(length of the string). The code is written under strict ANSI C.

For a complete understanding of the code see Ukkonen's algorithm and the
readme.txt file.

The general pseudo code is:

n = length of the string.
ST_CreateTree:
   Calls n times to SPA (Single Phase Algorithm). SPA:  
	  Increase the variable e (virtual end of all leaves).
   Calls SEA (Single Extension Algorithm) starting with the first extension that
   does not already exist in the tree and ending at the first extension that
   already exists. SEA :  
	  Follow suffix link.
	  Check if current suffix exists in the tree.
	  If it does not - apply rule 2 and then create a new suffix link.
	  apply_rule_2:  
		 Create a new leaf and maybe a new internal node as well.
		 create_node:  
			Create a new node or a leaf.


For implementation interpretations see Basic Ideas paragraph in the Developement
section of the readme.txt file.

An example of the implementations of a node and its sons using linked lists
instead of arrays:

   (1)
	|
	|
	|
   (2)--(3)--(4)--(5)

(2) is the only son of (1) (call it the first son). Other sons of (1) are
connected using a linked lists starting from (2) and going to the right. (3) is
the right sibling of (2) (and (2) is the left sibling of (3)), (4) is the right
sibling of (3), etc.
The father field of all (2), (3), (4) and (5) points to (1), but the son field
of (1) points only to (2).

*******************************************************************************/

//#include "stdlib.h"
//#include "stdio.h"
//#include "string.h"
//#include "suffix_tree.h"

/* See function body */
void ST_PrintTree(SUFFIX_TREE* tree);
/* See function body */
void ST_PrintFullNode(SUFFIX_TREE* tree, NODE* node);

/* Used in function trace_string for skipping (Ukkonen's Skip Trick). */
typedef enum SKIP_TYPE	 {skip, no_skip}				 SKIP_TYPE;
/* Used in function apply_rule_2 - two types of rule 2 - see function for more
   details.*/
typedef enum RULE_2_TYPE   {new_son, split}				RULE_2_TYPE;
/* Signals whether last matching position is the last one of the current edge */
typedef enum LAST_POS_TYPE {last_char_in_edge, other_char} LAST_POS_TYPE;

/* Used for statistic measures of speed. */
DBL_WORD counter;
/* Used for statistic measures of space. */
DBL_WORD heap;
/* Used to mark the node that has no suffix link yet. By Ukkonen, it will have
   one by the end of the current phase. */
NODE*	suffixless;

typedef struct SUFFIXTREEPATH
{
   DBL_WORD   begin;
   DBL_WORD   end;
} PATH;

typedef struct SUFFIXTREEPOS
{
   NODE*	  node;
   DBL_WORD   edge_pos;
}POS;

/******************************************************************************/
/*
   Define STATISTICS in order to view measures of speed and space while
   constructing and searching the suffix tree. Measures will be printed on the
   screen.
*/
/* #define STATISTICS */

/*
   Define DEBUG in order to view debug printouts to the screen while
   constructing and searching the suffix tree.
*/
/* #define DEBUG */

/******************************************************************************/
/*
   create_node :
   Creates a node with the given init field-values.

  Input : The father of the node, the starting and ending indices 
  of the incloming edge to that node, 
		the path starting position of the node.

  Output: A pointer to that node.
*/


NODE* create_node(NODE* father, DBL_WORD start, DBL_WORD end, DBL_WORD position)
{
   /*Allocate a node.*/
   NODE* node   = (NODE*)malloc(sizeof(NODE));
   if(node == 0)
   {
	  printf("\nOut of memory.\n");
	  exit(0);
   }

#ifdef STATISTICS
   heap+=sizeof(NODE);
#endif

   /* Initialize node fields. For detailed description of the fields see
	  suffix_tree.h */
   node->sons			 = 0;
   node->right_sibling	= 0;
   node->left_sibling	 = 0;
   node->suffix_link	  = 0;
   node->father		   = father;
   node->path_position	= position;
   node->edge_label_start = start;
   node->edge_label_end   = end;
   return node;
}

/******************************************************************************/
/*
   find_son :
   Finds son of node that starts with a certain character. 

   Input : the tree, the node to start searching from and the character to be
		   searched in the sons.
  
   Output: A pointer to the found son, 0 if no such son.
*/

NODE* find_son(SUFFIX_TREE* tree, NODE* node, char character)
{
   /* Point to the first son. */
   node = node->sons;
   /* scan all sons (all right siblings of the first son) for their first
   character (it has to match the character given as input to this function. */
   while(node != 0 && tree->tree_string[node->edge_label_start] != character)
   {
#ifdef STATISTICS
	  counter++;
#endif
	  node = node->right_sibling;
   }
   return node;
}

/******************************************************************************/
/*
   get_node_label_end :
   Returns the end index of the incoming edge to that node. This function is
   needed because for leaves the end index is not relevant, instead we must look
   at the variable "e" (the global virtual end of all leaves). Never refer
   directly to a leaf's end-index.

   Input : the tree, the node its end index we need.

   Output: The end index of that node (meaning the end index of the node's
   incoming edge).
*/

DBL_WORD get_node_label_end(SUFFIX_TREE* tree, NODE* node)
{
   /* If it's a leaf - return e */
   if(node->sons == 0)
	  return tree->e;
   /* If it's not a leaf - return its real end */
   return node->edge_label_end;
}

/******************************************************************************/
/*
   get_node_label_length :
   Returns the length of the incoming edge to that node. Uses get_node_label_end
   (see above).

   Input : The tree and the node its length we need.

   Output: the length of that node.
*/

DBL_WORD get_node_label_length(SUFFIX_TREE* tree, NODE* node)
{
   /* Calculate and return the lentgh of the node */
   return get_node_label_end(tree, node) - node->edge_label_start + 1;
}

/******************************************************************************/
/*
   is_last_char_in_edge :
   Returns 1 if edge_pos is the last position in node's incoming edge.

   Input : The tree, the node to be checked and the position in its incoming
		   edge.

   Output: the length of that node.
*/

char is_last_char_in_edge(SUFFIX_TREE* tree, NODE* node, DBL_WORD edge_pos)
{
   if(edge_pos == get_node_label_length(tree,node)-1)
	  return 1;
   return 0;
}

/******************************************************************************/
/*
   connect_siblings :
   Connect right_sib as the right sibling of left_sib and vice versa.

   Input : The two nodes to be connected.

   Output: None.
*/

void connect_siblings(NODE* left_sib, NODE* right_sib)
{
   /* Connect the right node as the right sibling of the left node */
   if(left_sib != 0)
	  left_sib->right_sibling = right_sib;
   /* Connect the left node as the left sibling of the right node */
   if(right_sib != 0)
	  right_sib->left_sibling = left_sib;
}

/******************************************************************************/
/*
   apply_extension_rule_2 :
   Apply "extension rule 2" in 2 cases:
   1. A new son (leaf 4) is added to a node that already has sons:
				(1)		   (1)
			   /   \	 ->   / | \
			  (2)  (3)	  (2)(3)(4)

   2. An edge is split and a new leaf (2) and an internal node (3) are added:
			  | 	  |
			  | 	 (3)
			  |	 ->   / \
			 (1)	   (1) (2)

   Input : See parameters.

   Output: A pointer to the newly created leaf (new_son case) or internal node
   (split case).
*/

NODE* apply_extension_rule_2(
					  /* Node 1 (see drawings) */
					  NODE*		   node,			
					  /* Start index of node 2's incoming edge */
					  DBL_WORD		edge_label_begin,   
					  /* End index of node 2's incoming edge */
					  DBL_WORD		edge_label_end,	  
					  /* Path start index of node 2 */
					  DBL_WORD		path_pos,		 
					  /* Position in node 1's incoming edge where split is to be
				 performed */
					  DBL_WORD		edge_pos,		 
					  /* Can be 'new_son' or 'split' */
					  RULE_2_TYPE	 type)			
{
   NODE *new_leaf,
		*new_internal,
		*son;
   /*-------new_son-------*/
   if(type == new_son)									   
   {
#ifdef DEBUG   
	  printf("rule 2: new leaf (%lu,%lu)\n",edge_label_begin,edge_label_end);
#endif
	  /* Create a new leaf (4) with the characters of the extension */
	  new_leaf = create_node(node, edge_label_begin , edge_label_end, path_pos);
	  /* Connect new_leaf (4) as the new son of node (1) */
	  son = node->sons;
	  while(son->right_sibling != 0)
		 son = son->right_sibling;
	  connect_siblings(son, new_leaf);
	  /* return (4) */
	  return new_leaf;
   }
   /*-------split-------*/
#ifdef DEBUG   
   printf("rule 2: split (%lu,%lu)\n",edge_label_begin,edge_label_end);
#endif
   /* Create a new internal node (3) at the split point */
   new_internal = create_node(
					  node->father,
					  node->edge_label_start,
					  node->edge_label_start+edge_pos,
					  node->path_position);
   /* Update the node (1) incoming edge starting index (it now starts where node
   (3) incoming edge ends) */
   node->edge_label_start += edge_pos+1;

   /* Create a new leaf (2) with the characters of the extension */
   new_leaf = create_node(
					  new_internal,
					  edge_label_begin,
					  edge_label_end,
					  path_pos);
   
   /* Connect new_internal (3) where node (1) was */
   /* Connect (3) with (1)'s left sibling */
   connect_siblings(node->left_sibling, new_internal);   
   /* connect (3) with (1)'s right sibling */
   connect_siblings(new_internal, node->right_sibling);
   node->left_sibling = 0;

   /* Connect (3) with (1)'s father */
   if(new_internal->father->sons == node)			
	  new_internal->father->sons = new_internal;
   
   /* Connect new_leaf (2) and node (1) as sons of new_internal (3) */
   new_internal->sons = node;
   node->father = new_internal;
   connect_siblings(node, new_leaf);
   /* return (3) */
   return new_internal;
}

/******************************************************************************/
/*
   trace_single_edge :
   Traces for a string in a given node's OUTcoming edge. It searches only in the
   given edge and not other ones. Search stops when either whole string was
   found in the given edge, a part of the string was found but the edge ended
   (and the next edge must be searched too - performed by function trace_string)
   or one non-matching character was found.

   Input : The string to be searched, given in indices of the main string.

   Output: (by value) the node where tracing has stopped.
		   (by reference) the edge position where last match occured, the string
	   position where last match occured, number of characters found, a flag
	   for signaling whether search is done, and a flag to signal whether
	   search stopped at a last character of an edge.
*/

NODE* trace_single_edge(
					  SUFFIX_TREE*	tree, 
					  /* Node to start from */
					  NODE*		   node,		 
					  /* String to trace */
					  PATH			str,		 
					  /* Last matching position in edge */
					  DBL_WORD*	   edge_pos,	  
					  /* Last matching position in tree source string */
					  DBL_WORD*	   chars_found,   
					  /* Skip or no_skip*/
					  SKIP_TYPE	   type,		  
					  /* 1 if search is done, 0 if not */
					  int*			search_done)   
{
   NODE*	  cont_node;
   DBL_WORD   length,str_len;

   /* Set default return values */
   *search_done = 1;
   *edge_pos	= 0;

   /* Search for the first character of the string in the outcoming edge of
	  node */
   cont_node = find_son(tree, node, tree->tree_string[str.begin]);
   if(cont_node == 0)
   {
	  /* Search is done, string not found */
	  *edge_pos = get_node_label_length(tree,node)-1;
	  *chars_found = 0;
	  return node;
   }
   
   /* Found first character - prepare for continuing the search */
   node	= cont_node;
   length  = get_node_label_length(tree,node);
   str_len = str.end - str.begin + 1;

   /* Compare edge length and string length. */
   /* If edge is shorter then the string being searched and skipping is
	  enabled - skip edge */
   if(type == skip)
   {
	  if(length <= str_len)
	  {
		 (*chars_found)   = length;
		 (*edge_pos)	  = length-1;
		 if(length < str_len)
			*search_done  = 0;
	  }
	  else
	  {
		 (*chars_found)   = str_len;
		 (*edge_pos)	  = str_len-1;
	  }

#ifdef STATISTICS
	  counter++;
#endif

	  return node;
   }
   else
   {
	  /* Find minimum out of edge length and string length, and scan it */
	  if(str_len < length)
		 length = str_len;

	  for(*edge_pos=1, *chars_found=1; *edge_pos<length; (*chars_found)++,(*edge_pos)++)
	  {

#ifdef STATISTICS
		 counter++;
#endif

		 /* Compare current characters of the string and the edge. If equal - 
		continue */
		 if(tree->tree_string[node->edge_label_start+*edge_pos] != tree->tree_string[str.begin+*edge_pos])
		 {
			(*edge_pos)--;
			return node;
		 }
	  }
   }

   /* The loop has advanced *edge_pos one too much */
   (*edge_pos)--;

   if((*chars_found) < str_len)
	  /* Search is not done yet */
	  *search_done = 0;

   return node;
}

/******************************************************************************/
/*
   trace_string :
   Traces for a string in the tree. This function is used in construction
   process only, and not for after-construction search of substrings. It is
   tailored to enable skipping (when we know a suffix is in the tree (when
   following a suffix link) we can avoid comparing all symbols of the edge by
   skipping its length immediately and thus save atomic operations - see
   Ukkonen's algorithm, skip trick).
   This function, in contradiction to the function trace_single_edge, 'sees' the
   whole picture, meaning it searches a string in the whole tree and not just in
   a specific edge.

   Input : The string, given in indice of the main string.

   Output: (by value) the node where tracing has stopped.
		   (by reference) the edge position where last match occured, the string
	   position where last match occured, number of characters found, a flag
	   for signaling whether search is done.
*/

NODE* trace_string(
					  SUFFIX_TREE*	tree, 
					  /* Node to start from */
					  NODE*		   node,		 
					  /* String to trace */
					  PATH			str,		 
					  /* Last matching position in edge */
					  DBL_WORD*	   edge_pos,	  
					  /* Last matching position in tree string */
					  DBL_WORD*	   chars_found,
					  /* skip or not */
					  SKIP_TYPE	   type)		 
{
   /* This variable will be 1 when search is done.
	  It is a return value from function trace_single_edge */
   int	  search_done = 0;

   /* This variable will hold the number of matching characters found in the
	  current edge. It is a return value from function trace_single_edge */
   DBL_WORD edge_chars_found;

   *chars_found = 0;

   while(search_done == 0)
   {
	  *edge_pos		= 0;
	  edge_chars_found = 0;
	  node = trace_single_edge(tree, node, str, edge_pos, &edge_chars_found, type, &search_done);
	  str.begin	   += edge_chars_found;
	  *chars_found	+= edge_chars_found;
   }
   return node;
}

/******************************************************************************/
/*
   ST_FindSubstring :
   See suffix_tree.h for description.
*/

DBL_WORD ST_FindSubstring(
					  /* The suffix array */
					  SUFFIX_TREE*	tree,	  
					  /* The substring to find */
					  char*  W,		 
					  /* The length of W */
					  DBL_WORD		P)		 
{
   /* Starts with the root's son that has the first character of W as its
	  incoming edge first character */
   NODE* node   = find_son(tree, tree->root, W[0]);
   DBL_WORD k,j = 0, node_label_end;

   /* Scan nodes down from the root untill a leaf is reached or the substring is
	  found */
   while(node!=0)
   {
	  k=node->edge_label_start;
	  node_label_end = get_node_label_end(tree,node);
	  
	  /* Scan a single edge - compare each character with the searched string */
	  while(j<P && k<=node_label_end && tree->tree_string[k] == W[j])
	  {
		 j++;
		 k++;

#ifdef STATISTICS
		 counter++;
#endif
	  }
	  
	  /* Checking which of the stopping conditions are true */
	  if(j == P)
	  {
		 /* W was found - it is a substring. Return its path starting index */
		 return node->path_position;
	  }
	  else if(k > node_label_end)
		 /* Current edge is found to match, continue to next edge */
		 node = find_son(tree, node, W[j]);
	  else
	  {
		 /* One non-matching symbols is found - W is not a substring */
		 return ST_ERROR;
	  }
   }
   return ST_ERROR;
}

/******************************************************************************/
/*
   follow_suffix_link :
   Follows the suffix link of the source node according to Ukkonen's rules. 

   Input : The tree, and pos. pos is a combination of the source node and the 
		   position in its incoming edge where suffix ends.
   Output: The destination node that represents the longest suffix of node's 
		   path. Example: if node represents the path "abcde" then it returns 
		   the node that represents "bcde".
*/

void follow_suffix_link(SUFFIX_TREE* tree, POS* pos)
{
   /* gama is the string between node and its father, in case node doesn't have
	  a suffix link */
   PATH	  gama;			
   /* dummy argument for trace_string function */
   DBL_WORD  chars_found = 0;   
   
   if(pos->node == tree->root)
   {
	  return;
   }

   /* If node has no suffix link yet or in the middle of an edge - remember the
	  edge between the node and its father (gama) and follow its father's suffix
	  link (it must have one by Ukkonen's lemma). After following, trace down 
	  gama - it must exist in the tree (and thus can use the skip trick - see 
	  trace_string function description) */
   if(pos->node->suffix_link == 0 || is_last_char_in_edge(tree,pos->node,pos->edge_pos) == 0)
   {
	  /* If the node's father is the root, than no use following it's link (it 
		 is linked to itself). Tracing from the root (like in the naive 
		 algorithm) is required and is done by the calling function SEA uppon 
		 recieving a return value of tree->root from this function */
	  if(pos->node->father == tree->root)
	  {
		 pos->node = tree->root;
		 return;
	  }
	  
	  /* Store gama - the indices of node's incoming edge */
	  gama.begin	  = pos->node->edge_label_start;
	  gama.end	  = pos->node->edge_label_start + pos->edge_pos;
	  /* Follow father's suffix link */
	  pos->node	  = pos->node->father->suffix_link;
	  /* Down-walk gama back to suffix_link's son */
	  pos->node	  = trace_string(tree, pos->node, gama, &(pos->edge_pos), &chars_found, skip);
   }
   else
   {
	  /* If a suffix link exists - just follow it */
	  pos->node	  = pos->node->suffix_link;
	  pos->edge_pos   = get_node_label_length(tree,pos->node)-1;
   }
}

/******************************************************************************/
/*
   create_suffix_link :
   Creates a suffix link between node and the node 'link' which represents its 
   largest suffix. The function could be avoided but is needed to monitor the 
   creation of suffix links when debuging or changing the tree.

   Input : The node to link from, the node to link to.

   Output: None.
*/

void create_suffix_link(NODE* node, NODE* link)
{
   node->suffix_link = link;
}

/******************************************************************************/
/*
   SEA :
   Single-Extension-Algorithm (see Ukkonen's algorithm). Ensure that a certain 
   extension is in the tree.

   1. Follows the current node's suffix link.
   2. Check whether the rest of the extension is in the tree.
   3. If it is - reports the calling function SPA of rule 3 (= current phase is 
	  done).
   4. If it's not - inserts it by applying rule 2.

   Input : The tree, pos - the node and position in its incoming edge where 
		   extension begins, str - the starting and ending indices of the 
		   extension, a flag indicating whether the last phase ended by rule 3 
		   (last extension of the last phase already existed in the tree - and 
		   if so, the current phase starts at not following the suffix link of 
		   the first extension).

   Output: The rule that was applied to that extension. Can be 3 (phase is done)
		   or 2 (a new leaf was created).
*/

void SEA(
					  SUFFIX_TREE*   tree, 
					  POS*		   pos,
					  PATH		   str, 
					  DBL_WORD*	  rule_applied,
					  char		   after_rule_3)
{
   DBL_WORD   chars_found = 0 , path_pos = str.begin;
   NODE*	  tmp;
 
#ifdef DEBUG   
   ST_PrintTree(tree);
   printf("extension: %lu  phase+1: %lu",str.begin, str.end);
   if(after_rule_3 == 0)
	  printf("   followed from (%lu,%lu | %lu) ", pos->node->edge_label_start, get_node_label_end(tree,pos->node), pos->edge_pos);
   else
	  printf("   starting at (%lu,%lu | %lu) ", pos->node->edge_label_start, get_node_label_end(tree,pos->node), pos->edge_pos);
#endif

#ifdef STATISTICS
   counter++;
#endif

   /* Follow suffix link only if it's not the first extension after rule 3 was applied */
   if(after_rule_3 == 0)
	  follow_suffix_link(tree, pos);

#ifdef DEBUG   
#ifdef STATISTICS
   if(after_rule_3 == 0)
	  printf("to (%lu,%lu | %lu). counter: %lu\n", pos->node->edge_label_start, get_node_label_end(tree,pos->node),pos->edge_pos,counter);
   else
	  printf(". counter: %lu\n", counter);
#endif
#endif

   /* If node is root - trace whole string starting from the root, else - trace last character only */
   if(pos->node == tree->root)
   {
	  pos->node = trace_string(tree, tree->root, str, &(pos->edge_pos), &chars_found, no_skip);
   }
   else
   {
	  str.begin = str.end;
	  chars_found = 0;

	  /* Consider 2 cases:
		 1. last character matched is the last of its edge */
	  if(is_last_char_in_edge(tree,pos->node,pos->edge_pos))
	  {
		 /* Trace only last symbol of str, search in the  NEXT edge (node) */
		 tmp = find_son(tree, pos->node, tree->tree_string[str.end]);
		 if(tmp != 0)
		 {
			pos->node	  = tmp;
			pos->edge_pos   = 0;
			chars_found	  = 1;
		 }
	  }
	  /* 2. last character matched is NOT the last of its edge */
	  else
	  {
		 /* Trace only last symbol of str, search in the CURRENT edge (node) */
		 if(tree->tree_string[pos->node->edge_label_start+pos->edge_pos+1] == tree->tree_string[str.end])
		 {
			pos->edge_pos++;
			chars_found   = 1;
		 }
	  }
   }

   /* If whole string was found - rule 3 applies */
   if(chars_found == str.end - str.begin + 1)
   {
	  *rule_applied = 3;
	  /* If there is an internal node that has no suffix link yet (only one may 
		 exist) - create a suffix link from it to the father-node of the 
		 current position in the tree (pos) */
	  if(suffixless != 0)
	  {
		 create_suffix_link(suffixless, pos->node->father);
		 /* Marks that no internal node with no suffix link exists */
		 suffixless = 0;
	  }

	  #ifdef DEBUG   
		 printf("rule 3 (%lu,%lu)\n",str.begin,str.end);
	  #endif
	  return;
   }
   
   /* If last char found is the last char of an edge - add a character at the 
	  next edge */
   if(is_last_char_in_edge(tree,pos->node,pos->edge_pos) || pos->node == tree->root)
   {
	  /* Decide whether to apply rule 2 (new_son) or rule 1 */
	  if(pos->node->sons != 0)
	  {
		 /* Apply extension rule 2 new son - a new leaf is created and returned 
			by apply_extension_rule_2 */
		 apply_extension_rule_2(pos->node, str.begin+chars_found, str.end, path_pos, 0, new_son);
		 *rule_applied = 2;
		 /* If there is an internal node that has no suffix link yet (only one 
			may exist) - create a suffix link from it to the father-node of the 
			current position in the tree (pos) */
		 if(suffixless != 0)
		 {
			create_suffix_link(suffixless, pos->node);
			/* Marks that no internal node with no suffix link exists */
			suffixless = 0;
		 }
	  }
   }
   else
   {
	  /* Apply extension rule 2 split - a new node is created and returned by 
		 apply_extension_rule_2 */
	  tmp = apply_extension_rule_2(pos->node, str.begin+chars_found, str.end, path_pos, pos->edge_pos, split);
	  if(suffixless != 0)
		 create_suffix_link(suffixless, tmp);
	  /* Link root's sons with a single character to the root */
	  if(get_node_label_length(tree,tmp) == 1 && tmp->father == tree->root)
	  {
		 tmp->suffix_link = tree->root;
		 /* Marks that no internal node with no suffix link exists */
		 suffixless = 0;
	  }
	  else
		 /* Mark tmp as waiting for a link */
		 suffixless = tmp;
	  
	  /* Prepare pos for the next extension */
	  pos->node = tmp;
	  *rule_applied = 2;
   }
}

/******************************************************************************/
/*
   SPA :
   Performs all insertion of a single phase by calling function SEA starting 
   from the first extension that does not already exist in the tree and ending 
   at the first extension that already exists in the tree. 

   Input :The tree, pos - the node and position in its incoming edge where 
		  extension begins, the phase number, the first extension number of that
		  phase, a flag signaling whether the extension is the first of this 
		  phase, after the last phase ended with rule 3. If so - extension will 
		  be executed again in this phase, and thus its suffix link would not be
		  followed.

   Output:The extension number that was last executed on this phase. Next phase 
		  will start from it and not from 1
*/

void SPA(
					  /* The tree */
					  SUFFIX_TREE*	tree,			
					  /* Current node */
					  POS*			pos,			
					  /* Current phase number */
					  DBL_WORD		phase,			
					  /* The last extension performed in the previous phase */
					  DBL_WORD*	   extension,		 
					  /* 1 if the last rule applied is 3 */
					  char*		   repeated_extension)   
{
   /* No such rule (0). Used for entering the loop */
   DBL_WORD   rule_applied = 0;   
   PATH	   str;
   
   /* Leafs Trick: Apply implicit extensions 1 through prev_phase */
   tree->e = phase+1;

   /* Apply explicit extensions untill last extension of this phase is reached 
	  or extension rule 3 is applied once */
   while(*extension <= phase+1)			
   {
	  str.begin	   = *extension;
	  str.end		 = phase+1;
	  
	  /* Call Single-Extension-Algorithm */
	  SEA(tree, pos, str, &rule_applied, *repeated_extension);
	  
	  /* Check if rule 3 was applied for the current extension */
	  if(rule_applied == 3)
	  {
		 /* Signaling that the next phase's first extension will not follow a 
			suffix link because same extension is repeated */
		 *repeated_extension = 1;
		 break;
	  }
	  *repeated_extension = 0;
	  (*extension)++;
   }
   return;
}

/******************************************************************************/
/*
   ST_CreateTree :
   Allocates memory for the tree and starts Ukkonen's construction algorithm by 
   calling SPA n times, where n is the length of the source string.

   Input : The source string and its length. The string is a sequence of 
		   unsigned characters (maximum of 256 different symbols) and not 
		   null-terminated. The only symbol that must not appear in the string 
		   is $ (the dollar sign). It is used as a unique symbol by the 
		   algorithm ans is appended automatically at the end of the string (by 
		   the program, not by the user!). The meaning of the $ sign is 
		   connected to the implicit/explicit suffix tree transformation, 
		   detailed in Ukkonen's algorithm.

   Output: A pointer to the newly created tree. Keep this pointer in order to 
		   perform operations like search and delete on that tree. Obviously, no
	   de-allocating of the tree space could be done if this pointer is 
	   lost, as the tree is allocated dynamically on the heap.
*/

SUFFIX_TREE* ST_CreateTree(const char* str, DBL_WORD length)
{
   SUFFIX_TREE*  tree;
   DBL_WORD	  phase , extension;
   char		  repeated_extension = 0;
   POS		   pos;

   if(str == 0)
	  return 0;

   /* Allocating the tree */
   tree = (SUFFIX_TREE*)malloc(sizeof(SUFFIX_TREE));
   if(tree == 0)
   {
	  printf("\nOut of memory.\n");
	  exit(0);
   }
   heap+=sizeof(SUFFIX_TREE);

   /* Calculating string length (with an ending $ sign) */
   tree->length		 = length+1;
   ST_ERROR			= length+10;
   
   /* Allocating the only real string of the tree */
   tree->tree_string = (char*)malloc((tree->length+1)*sizeof(char));
   if(tree->tree_string == 0)
   {
	  printf("\nOut of memory.\n");
	  exit(0);
   }
   heap+=(tree->length+1)*sizeof(char);

   memcpy(tree->tree_string+sizeof(char),str,length*sizeof(char));
   /* $ is considered a uniqe symbol */
   tree->tree_string[tree->length] = '$';
   
   /* Allocating the tree root node */
   tree->root			= create_node(0, 0, 0, 0);
   tree->root->suffix_link = 0;

   /* Initializing algorithm parameters */
   extension = 2;
   phase = 2;
   
   /* Allocating first node, son of the root (phase 0), the longest path node */
   tree->root->sons = create_node(tree->root, 1, tree->length, 1);
   suffixless	   = 0;
   pos.node		 = tree->root;
   pos.edge_pos	 = 0;

   /* Ukkonen's algorithm begins here */
   for(; phase < tree->length; phase++)
   {
	  /* Perform Single Phase Algorithm */
	  SPA(tree, &pos, phase, &extension, &repeated_extension);
   }
   return tree;
}

/******************************************************************************/
/*
   ST_DeleteSubTree :
   Deletes a subtree that is under node. It recoursively calls itself for all of
   node's right sons and then deletes node.

  Input : The node that is the root of the subtree to be deleted.

  Output: None.
*/

void ST_DeleteSubTree(NODE* node)
{
   /* Recoursion stoping condition */
   if(node == 0)
	  return;
   /* Recoursive call for right sibling */
   if(node->right_sibling!=0)
	  ST_DeleteSubTree(node->right_sibling);
   /* Recoursive call for first son */
   if(node->sons!=0)
	  ST_DeleteSubTree(node->sons);
   /* Delete node itself, after its whole tree was deleted as well */
   free(node);
}

/******************************************************************************/
/*
   ST_DeleteTree :
   Deletes a whole suffix tree by starting a recoursive call to ST_DeleteSubTree
   from the root. After all of the nodes have been deleted, the function deletes
   the structure that represents the tree.

   Input : The tree to be deleted.

   Output: None.
*/

void ST_DeleteTree(SUFFIX_TREE* tree)
{
   if(tree == 0)
	  return;
   ST_DeleteSubTree(tree->root);
   free(tree);
}

/******************************************************************************/
/*
   ST_PrintNode :
   Prints a subtree under a node of a certain tree-depth.

   Input : The tree, the node that is the root of the subtree, and the depth of 
		   that node. The depth is used for printing the branches that are 
		   coming from higher nodes and only then the node itself is printed. 
		   This gives the effect of a tree on screen. In each recoursive call, 
		   the depth is increased.
  
   Output: A printout of the subtree to the screen.
*/

void ST_PrintNode(SUFFIX_TREE* tree, NODE* node1, long depth)
{
   NODE* node2 = node1->sons;
   long  d = depth , start = node1->edge_label_start , end;
   end	 = get_node_label_end(tree, node1);

   if(depth>0)
   {
	  /* Print the branches coming from higher nodes */
	  while(d>1)
	  {
		 printf("|");
		 d--;
	  }
	  printf("+");
	  /* Print the node itself */
	  while(start<=end)
	  {
		 printf("%c",tree->tree_string[start]);
		 start++;
	  }
		 printf("  \t\t\t(%lu,%lu | %lu)",node1->edge_label_start,end,node1->path_position);
		 printf("(data=%s)", RenderPerNodeData(*node1->more_data).c_str());
	  printf("\n");
   } else {
		 printf("(data=%s)\n", RenderPerNodeData(*node1->more_data).c_str());
   }
   /* Recoursive call for all node1's sons */
   while(node2!=0)
   {
	  ST_PrintNode(tree,node2, depth+1);
	  node2 = node2->right_sibling;
   }
}

/******************************************************************************/
/*
   ST_PrintFullNode :
   This function prints the full path of a node, starting from the root. It 
   calls itself recoursively and than prints the last edge.

   Input : the tree and the node its path is to be printed.

   Output: Prints the path to the screen, no return value.
*/

void ST_PrintFullNode(SUFFIX_TREE* tree, NODE* node)
{
   long start, end;
   if(node==NULL)
	  return;
   /* Calculating the begining and ending of the last edge */
   start   = node->edge_label_start;
   end	 = get_node_label_end(tree, node);
   
   /* Stoping condition - the root */
   if(node->father!=tree->root)
	  ST_PrintFullNode(tree,node->father);
   /* Print the last edge */
   while(start<=end)
   {
	  printf("%c",tree->tree_string[start]);
	  start++;
   }
}


/******************************************************************************/
/*
   ST_PrintTree :
   This function prints the tree. It simply starts the recoursive function 
   ST_PrintNode with depth 0 (the root).

   Input : The tree to be printed.
  
   Output: A print out of the tree to the screen.
*/

void ST_PrintTree(SUFFIX_TREE* tree)
{
   printf("\nroot\n");
   ST_PrintNode(tree, tree->root, 0);
}

/******************************************************************************/
/*
   ST_SelfTest :
   Self test of the tree - search for all substrings of the main string. See 
   testing paragraph in the readme.txt file.

   Input : The tree to test.

   Output: 1 for success and 0 for failure. Prints a result message to the screen.
*/

DBL_WORD ST_SelfTest(SUFFIX_TREE* tree)
{
   DBL_WORD k,j,i;

#ifdef STATISTICS
   DBL_WORD old_counter = counter;
#endif

   /* Loop for all the prefixes of the tree source string */
   for(k = 1; k<tree->length; k++)
   {
	  /* Loop for each suffix of each prefix */
	  for(j = 1; j<=k; j++)
	  {
#ifdef STATISTICS
		 counter = 0;
#endif
		 /* Search the current suffix in the tree */
		 i = ST_FindSubstring(tree, (char*)(tree->tree_string+j), k-j+1);
		 if(i == ST_ERROR)
		 {
			printf("\n\nTest Results: Fail in string (%lu,%lu).\n\n",j,k);
			return 0;
		 }
	  }
   }
#ifdef STATISTICS
   counter = old_counter;
#endif
   /* If we are here no search has failed and the test passed successfuly */
   printf("\n\nTest Results: Success.\n\n");
   return 1;
}

// End borrowed code.

struct DataPoint {
	int curr_i, next_i, min_d, max_d;

	void UpdateWithDump(int depth, int new_next) const;
};
inline bool operator<(const DataPoint& a, const DataPoint& b) {
	return a.curr_i < b.curr_i;
}

vector<DataPoint> dumped_dps;

void DataPoint::UpdateWithDump(int depth, int new_next) const {
	if (depth < max_d) {
		dumped_dps.push_back({curr_i, next_i, depth, max_d});
	}
	auto* t = const_cast<DataPoint*>(this);
	t->next_i = new_next;
	t->max_d = depth;
}

struct PerNodeData {
	int depth;
	set<DataPoint> data_points;
};
string RenderPerNodeData(const PerNodeData& data) {
	ostringstream s;
	s << "{";
	s << "d=" << data.depth;
	s << "}";
	return s.str();;
}

deque<PerNodeData> data_pool;

void AssignPerNodeData(NODE* node) {
	data_pool.emplace_back();
	node->more_data = &data_pool.back();
	for (NODE* p = node->sons; p; p = p->right_sibling) {
		AssignPerNodeData(p);
	}
}

SUFFIX_TREE* tree;
string S;

pair<const char*, const char*> GetLeadingString(NODE* p) {
	const char* start = tree->tree_string + p->edge_label_start;
	const char* end = tree->tree_string + get_node_label_end(tree, p) + 1;
	return make_pair(start, end);
}

void MergeDataPoints(set<DataPoint>& base, vector<set<DataPoint>>& to_merge,
					 int depth) {
	typedef pair<DataPoint, set<DataPoint>*> QElem;
	struct DPGreater {
		bool operator()(const QElem& a, const QElem& b) {
			return b.first < a.first;
		}
	};
	static priority_queue<QElem, vector<QElem>, DPGreater> Q;
	for (auto& dps : to_merge) {
		if (dps.empty()) { continue; }
		Q.emplace(*dps.begin(), &dps);
		dps.erase(dps.begin());
	}
	auto base_iter = base.begin();
	while (!Q.empty()) {
		set<DataPoint>::iterator iter = base.emplace_hint(base_iter, Q.top().first);
		{
			auto* dps = Q.top().second;
			Q.pop();
			if (!dps->empty()) {
				Q.emplace(*dps->begin(), dps);
				dps->erase(dps->begin());
			}
		}
		if (iter != base.begin()) {
			auto p = prev(iter);
			p->UpdateWithDump(depth, iter->curr_i);
		}
		if (next(iter) != base.end()) {
			iter->UpdateWithDump(depth, next(iter)->curr_i);
		}
		base_iter = iter;
	}
}

void ComputePerNodeData(NODE* node) {
	for (NODE* p = node->sons; p; p = p->right_sibling) {
		{
			auto t = GetLeadingString(p);
			p->more_data->depth = node->more_data->depth + (t.second - t.first);
		}
		ComputePerNodeData(p);
	}
	if (node->sons == 0) {  // Leaf.
		DataPoint p;
		int depth = node->more_data->depth - 1; // exclude "$"
		p.curr_i = get_node_label_end(tree, node) - depth - 1;
		p.next_i = S.size() + 1;
		p.min_d = -1;
		p.max_d = depth;
		auto& dps = node->more_data->data_points;
		dps.clear();
		dps.insert(p);
	} else {
		static vector<set<DataPoint>> to_merge;
		to_merge.clear();
		for (NODE* p = node->sons; p; p = p->right_sibling) {
			to_merge.push_back(std::move(p->more_data->data_points));
		}
		auto max_iter = max_element(to_merge.begin(), to_merge.end(),
				[](const set<DataPoint>& a, const set<DataPoint>& b) {
					return a.size() < b.size();
				});
		check(max_iter != to_merge.end());
		set<DataPoint> base = std::move(*max_iter);
		to_merge.erase(max_iter);
		MergeDataPoints(base, to_merge, node->more_data->depth);
		node->more_data->data_points = std::move(base);
	}
}

struct Task {
	int L, R, id;
	ll ans;
};
vector<Task> tasks;

struct Poly {
	ll a1, a0;

	Poly(ll _a1, ll _a0) : a1(_a1), a0(_a0) {}

	ll operator()(ll X) const { return a1 * X + a0; }

	Poly& operator+=(const Poly& o) {
		a1 += o.a1;
		a0 += o.a0;
		return *this;
	}
};

struct RangeTree {
	void Init(int size) {
		for (N = 1; N < size; N *= 2);
		p.assign(N * 2 - 1, Poly(0, 0));
	}

	void Update(int pos, const Poly& v) {
		pos += N - 1;
		for (;;) {
			p[pos] += v;
			if (IsRoot(pos)) { break; }
			pos = Fa(pos);
		}
	}

	Poly Get(int pos) const {
		pos += N - 1;
		Poly ans = p[pos];
		while (!IsRoot(pos)) {
			int f = Fa(pos);
			if (pos == LCh(f)) { ans += p[RCh(f)]; }
			pos = f;
		}
		return ans;
	}

private:
	int N;
	vector<Poly> p;

	static bool IsRoot(int p) { return p == 0; }
	static int Fa(int p) { return (p - 1) / 2; }
	static int LCh(int p) { return p * 2 + 1; }
	static int RCh(int p) { return p * 2 + 2; }
};

void SolveBatch() {
	struct PtPoly {
		int a;
		Poly p;
		PtPoly* next = nullptr;

		PtPoly(int _a, const Poly& _p) : a(_a), p(_p) {}
	};
	vector<pair<int, PtPoly>> events;
	events.reserve(dumped_dps.size() * 4);
	int max_timestamp = 0;
	for (const auto& dp : dumped_dps) {
		int lo = dp.min_d, hi = dp.max_d, c = dp.curr_i, n = dp.next_i;
		events.emplace_back(lo + c, PtPoly(c, Poly(+1, -(lo + c))));
		events.emplace_back(lo + n, PtPoly(c, Poly(-1, +(lo + n))));
		events.emplace_back(hi + c, PtPoly(c, Poly(-1, +(hi + c))));
		events.emplace_back(hi + n, PtPoly(c, Poly(+1, -(hi + n))));
		max_timestamp = max(max_timestamp, hi + n);
	}
	vector<PtPoly*> heads(max_timestamp + 1, nullptr);
	for (auto& e : events) {
		e.second.next = heads[e.first];
		heads[e.first] = &e.second;
	}
	sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
		return a.R < b.R;
	});
	auto t_iter = tasks.begin();
	RangeTree tree;
	tree.Init(S.size() + 1);
	for (int timestamp = 0; timestamp < heads.size(); ++timestamp) {
		for (PtPoly* pt = heads[timestamp]; pt != nullptr; pt = pt->next) {
			tree.Update(pt->a, pt->p);
		}
		for (; t_iter != tasks.end() && t_iter->R == timestamp; ++t_iter) {
			Poly p = tree.Get(t_iter->L);
			t_iter->ans = p(t_iter->R);
		}
	}
}

int main() {
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	int N, Q;
	cin >> N >> Q >> S;
	tree = ST_CreateTree(S.c_str(), (int)S.size());
	AssignPerNodeData(tree->root);
	tree->root->more_data->depth = 0;
	ComputePerNodeData(tree->root);
	for (const DataPoint& dp : tree->root->more_data->data_points) {
		dp.UpdateWithDump(0, S.size() + 1);
	}
	tasks.resize(Q);
	for (int i = 0; i < Q; ++i) {
		Task& t = tasks[i];
		t.id = i;
		cin >> t.L >> t.R;
		++t.R;
		t.ans = 0;
	}
	SolveBatch();
	sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
		return a.id < b.id;
	});
	for (Task& t : tasks) {
		cout << t.ans << '\n';
	}

	return 0;
}


Java How Many Substrings? HackerRank Solution


Copy Code Copied Use a different Browser

 

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.List;

public class G2 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), Q = ni();
		char[] s = ns(n);
		int[][] qs = new int[Q][];
		for(int z = 0;z < Q;z++){
			qs[z] = new int[]{ni(), ni(), z};
		}
		Arrays.sort(qs, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[1] - b[1];
			}
		});
	
		
		SuffixAutomatonOfBit sa = SuffixAutomatonOfBit.build(s);
		sa.sortTopologically();
		SuffixAutomatonOfBit.Node[] nodes = sa.nodes;
		int[] from = new int[nodes.length-1];
		int[] to = new int[nodes.length-1];
		int p = 0;
		for(SuffixAutomatonOfBit.Node node : nodes){
			if(node.id >= 1){
				from[p] = node.link.id; to[p] = node.id; p++;
			}
		}
		assert p == nodes.length-1;
		int[][] g = packU(nodes.length, from, to);
		int[][] pars = parents3(g, 0);
		int[] par = pars[0], ord = pars[1], dep = pars[2];
		HeavyLightDecomposition hld = new HeavyLightDecomposition(g, par, ord, dep);
		int m = hld.cluspath.length;
		SegmentTreeOverwrite[] sts = new SegmentTreeOverwrite[m];
		for(int i = 0;i < m;i++){
			sts[i] = new SegmentTreeOverwrite(hld.cluspath[i].length);
		}
		
		int[] base = new int[n];
		int qp = 0;
		int np = 0;
		long[] ft0 = new long[n+3];
		long[] ft1 = new long[n+3];
		long[] ans = new long[Q];
		for(int i = 0;i < n;i++){
			while(!(nodes[np].len == i+1 && nodes[np].original == null))np++;
			base[i] = np;

			int ppos = 0;
			while(true){
				int last = sts[hld.clus[cur]].get(hld.clusiind[cur]);
				if(last == -1)break;
				int lca = hld.lca(base[last], base[i]);
				// delete from lca to cur
				int inf = last-nodes[lca].len+1;
				int sup = last-ppos+1;

				addFenwick(ft0, 0, -(sup-inf));
				addFenwick(ft0, sup+1, +(sup-inf));
				addFenwick(ft0, inf+1, -(inf+1));
				addFenwick(ft0, sup+1, +inf+1);
				addFenwick(ft1, inf+1, 1);
				addFenwick(ft1, sup+1, -1);
				ppos = nodes[lca].len;
				assert dep[base[i]]-dep[lca]-1 >= 0;
				cur = hld.ancestor(base[i], dep[base[i]]-dep[lca]-1);
			}

			int cx = hld.clus[base[i]]; // cluster
			int ind = hld.clusiind[base[i]]; // pos in cluster
			while(true){
				sts[cx].update(0, ind+1, i);
				int con = par[hld.cluspath[cx][0]];
				if(con == -1)break;
				ind = hld.clusiind[con];
				cx = hld.clus[con];
			}
			
			addFenwick(ft0, 0, i+1+1);
			addFenwick(ft0, i+1+1, -(i+1+1));
			addFenwick(ft1, 0, -1);
			addFenwick(ft1, i+1+1, 1);
			
			while(qp < Q && qs[qp][1] <= i){
				ans[qs[qp][2]] = sumRangeFenwick(ft0, ft1, qs[qp][0]);
				qp++;
			}
		}
		for(long an : ans){
			out.println(an);
		}
	}
	
	public static long sumFenwick(long[] ft, int i)
	{
		long sum = 0;
		for(i++;i > 0;i -= i&-i)sum += ft[i];
		return sum;
	}
	
	public static void addFenwick(long[] ft, int i, long v)
	{
		if(v == 0)return;
		int n = ft.length;
		for(i++;i < n;i += i&-i)ft[i] += v;
	}
	
	public static int firstGEFenwick(long[] ft, long v)
	{
		int i = 0, n = ft.length;
		for(int b = Integer.highestOneBit(n);b != 0;b >>= 1){
			if((i|b) < n && ft[i|b] < v){
				i |= b;
				v -= ft[i];
			}
		}
		return i;
	}
	
	public static long[] restoreFenwick(long[] ft)
	{
		int n = ft.length-1;
		long[] ret = new long[n];
		for(int i = 0;i < n;i++)ret[i] = sumFenwick(ft, i);
		for(int i = n-1;i >= 1;i--)ret[i] -= ret[i-1];
		return ret;
	}
	
	public static int findGFenwick(long[] ft, long v)
	{
		int i = 0;
		int n = ft.length;
		for(int b = Integer.highestOneBit(n);b != 0 && i < n;b >>= 1){
			if(i + b < n){
				int t = i + b;
				if(v >= ft[t]){
					i = t;
					v -= ft[t];
				}
			}
		}
		return v != 0 ? -(i+1) : i-1;
	}
	
	public static long[] buildFenwick(long[] a)
	{
		int n = a.length;
		long[] ft = new long[n+1];
		System.arraycopy(a, 0, ft, 1, n);
		for(int k = 2, h = 1;k <= n;k*=2, h*=2){
			for(int i = k;i <= n;i+=k){
				ft[i] += ft[i-h];
			}
		}
		return ft;
	}
	
	public static void addRangeFenwick(long[] ft0, long[] ft1, int i, long v)
	{
		addFenwick(ft1, i+1, -v);
		addFenwick(ft1, 0, v);
		addFenwick(ft0, i+1, v*(i+1));
	}
	
	public static void addRangeFenwick(long[] ft0, long[] ft1, int a, int b, long v)
	{
		if(a <= b){
			addFenwick(ft1, b+1, -v);
			addFenwick(ft0, b+1, v*(b+1));
			addFenwick(ft1, a, v);
			addFenwick(ft0, a, -v*a);
		}
	}
	
	public static long sumRangeFenwick(long[] ft0, long[] ft1, int i)
	{
		return sumFenwick(ft1, i) * (i+1) + sumFenwick(ft0, i);
	}
	
	public static long[] restoreRangeFenwick(long[] ft0, long[] ft1)
	{
		int n = ft0.length-1;
		long[] ret = new long[n];
		for(int i = 0;i < n;i++)ret[i] = sumRangeFenwick(ft0, ft1, i);
		for(int i = n-1;i >= 1;i--)ret[i] -= ret[i-1];
		return ret;
	}

	
	public static class SegmentTreeOverwrite {
		public int M, H, N;
		public int[] cover;
		public int I = Integer.MAX_VALUE;
		
		public SegmentTreeOverwrite(int len)
		{
			N = len;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			cover = new int[M];
			Arrays.fill(cover, I);
			for(int i = 0;i < N;i++){
				cover[H+i] = -1;
			}
			for(int i = H-1;i >= 1;i--){
				propagate(i);
			}
		}
		
		private void propagate(int i){}
		
		public void update(int l, int r, int v){ update(l, r, v, 0, H, 1); }
		
		private void update(int l, int r, int v, int cl, int cr, int cur)
		{
			if(l <= cl && cr <= r){
				cover[cur] = v;
				propagate(cur);
			}else{
				int mid = cl+cr>>>1;
				if(cover[cur] != I){ // back-propagate
					cover[2*cur] = cover[2*cur+1] = cover[cur];
					cover[cur] = I;
					propagate(2*cur);
					propagate(2*cur+1);
				}
				if(cl < r && l < mid){
					update(l, r, v, cl, mid, 2*cur);
				}
				if(mid < r && l < cr){
					update(l, r, v, mid, cr, 2*cur+1);
				}
				propagate(cur);
			}
		}
		
		public int get(int x){ 
			int val = I;
			for(int i = H+x;i >= 1;i>>>=1){
				if(cover[i] != I)val = cover[i];
			}
			return val;
		}
	}

	
	public static class HeavyLightDecomposition {
		public int[] clus;
		public int[][] cluspath;
		public int[] clusiind;
		public int[] par, dep;
		
		public HeavyLightDecomposition(int[][] g, int[] par, int[] ord, int[] dep)
		{
			init(g, par, ord, dep);
		}
		
		public void init(int[][] g, int[] par, int[] ord, int[] dep)
		{
			clus = decomposeToHeavyLight(g, par, ord);
			cluspath = clusPaths(clus, ord);
			clusiind = clusIInd(cluspath, g.length);
			this.par = par;
			this.dep = dep;
		}
		
		public static int[] decomposeToHeavyLight(int[][] g, int[] par, int[] ord)
		{
			int n = g.length;
			int[] size = new int[n];
			Arrays.fill(size, 1);
			for(int i = n-1;i > 0;i--)size[par[ord[i]]] += size[ord[i]];
			
			int[] clus = new int[n];
			Arrays.fill(clus, -1);
			int p = 0;
			for(int i = 0;i < n;i++){
				int u = ord[i];
				if(clus[u] == -1)clus[u] = p++;
				// centroid path (not heavy path)
				int argmax = -1;
				for(int v : g[u]){
					if(par[u] != v && (argmax == -1 || size[v] > size[argmax]))argmax = v;
				}
				if(argmax != -1)clus[argmax] = clus[u];
			}
			return clus;
		}
		
		public static int[][] clusPaths(int[] clus, int[] ord)
		{
			int n = clus.length;
			int[] rp = new int[n];
			int sup = 0;
			for(int i = 0;i < n;i++){
				rp[clus[i]]++;
				sup = Math.max(sup, clus[i]);
			}
			sup++;
			
			int[][] row = new int[sup][];
			for(int i = 0;i < sup;i++)row[i] = new int[rp[i]];
			
			for(int i = n-1;i >= 0;i--){
				row[clus[ord[i]]][--rp[clus[ord[i]]]] = ord[i];
			}
			return row;
		}
		
		public static int[] clusIInd(int[][] clusPath, int n)
		{
			int[] iind = new int[n];
			for(int[] path : clusPath){
				for(int i = 0;i < path.length;i++){
					iind[path[i]] = i;
				}
			}
			return iind;
		}
		
		public int lca(int x, int y)
		{
			int rx = cluspath[clus[x]][0];
			int ry = cluspath[clus[y]][0];
			while(clus[x] != clus[y]){
				if(dep[rx] > dep[ry]){
					x = par[rx];
					rx = cluspath[clus[x]][0];
				}else{
					y = par[ry];
					ry = cluspath[clus[y]][0];
				}
			}
			return clusiind[x] > clusiind[y] ? y : x;
		}
		
		public int ancestor(int x, int v)
		{
			while(x != -1){
				if(v <= clusiind[x])return cluspath[clus[x]][clusiind[x]-v];
				v -= clusiind[x]+1;
				x = par[cluspath[clus[x]][0]];
			}
			return x;
		}
	}

	
	public static int lca2(int a, int b, int[][] spar, int[] depth) {
		if (depth[a] < depth[b]) {
			b = ancestor(b, depth[b] - depth[a], spar);
		} else if (depth[a] > depth[b]) {
			a = ancestor(a, depth[a] - depth[b], spar);
		}

		if (a == b)
			return a;
		int sa = a, sb = b;
		for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
				.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
			if ((low ^ high) >= t) {
				if (spar[k][sa] != spar[k][sb]) {
					low |= t;
					sa = spar[k][sa];
					sb = spar[k][sb];
				} else {
					high = low | t - 1;
				}
			}
		}
		return spar[0][sa];
	}

	protected static int ancestor(int a, int m, int[][] spar) {
		for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
			if ((m & 1) == 1)
				a = spar[i][a];
		}
		return a;
	}

	public static int[][] logstepParents(int[] par) {
		int n = par.length;
		int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
		int[][] pars = new int[m][n];
		pars[0] = par;
		for (int j = 1; j < m; j++) {
			for (int i = 0; i < n; i++) {
				pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
			}
		}
		return pars;
	}

	
	public static int[][] parents3(int[][] g, int root) {
		int n = g.length;
		int[] par = new int[n];
		Arrays.fill(par, -1);

		int[] depth = new int[n];
		depth[0] = 0;

		int[] q = new int[n];
		q[0] = root;
		for (int p = 0, r = 1; p < r; p++) {
			int cur = q[p];
			for (int nex : g[cur]) {
				if (par[cur] != nex) {
					q[r++] = nex;
					par[nex] = cur;
					depth[nex] = depth[cur] + 1;
				}
			}
		}
		return new int[][] { par, q, depth };
	}

	
	static int[][] packU(int n, int[] from, int[] to) {
		int[][] g = new int[n][];
		int[] p = new int[n];
		for (int f : from)
			p[f]++;
		for (int t : to)
			p[t]++;
		for (int i = 0; i < n; i++)
			g[i] = new int[p[i]];
		for (int i = 0; i < from.length; i++) {
			g[from[i]][--p[from[i]]] = to[i];
			g[to[i]][--p[to[i]]] = from[i];
		}
		return g;
	}
	
	public static class SuffixAutomatonOfBit {
		public Node t0;
		public int len;
		public Node[] nodes;
		public int gen;
		private boolean sortedTopologically = false;
		private boolean lexsorted = false;
		
		private SuffixAutomatonOfBit(int n)
		{
			gen = 0;
			nodes = new Node[2*n];
			this.t0 = makeNode(0, null);
		}
		
		private Node makeNode(int len, Node original)
		{
			Node node = new Node();
			node.id = gen;
			node.original = original;
			node.len = len;
			nodes[gen++] = node;
			return node;
		}
		
		public static class Node
		{
			public int id;
			public int len;
			public char key;
			public Node link;
			private Node[] next = new Node[3];
			public Node original;
			public int np = 0;
			public int hit = 0;
			
			public void putNext(char c, Node to)
			{
				to.key = c;
				if(hit<<~(c-'a')<0){
					for(int i = 0;i < np;i++){
						if(next[i].key == c){
							next[i] = to;
							return;
						}
					}
				}
				hit |= 1<<c-'a';
				if(np == next.length){
					next = Arrays.copyOf(next, np*2);
				}
				next[np++] = to;
			}
			
			public boolean containsKeyNext(char c)
			{
				return hit<<~(c-'a')<0;
//				for(int i = 0;i < np;i++){
//					if(next[i].key == c)return true;
//				}
//				return false;
			}
			
			public Node getNext(char c)
			{
				if(hit<<~(c-'a')<0){
					for(int i = 0;i < np;i++){
						if(next[i].key == c)return next[i];
					}
				}
				return null;
			}
			
			public List<String> suffixes(char[] s)
			{
				List<String> list = new ArrayList<String>();
				if(id == 0)return list;
				int first = original != null ? original.len : len;
				for(int i = link.len + 1;i <= len;i++){
					list.add(new String(s, first - i, i));
				}
				return list;
			}
		}

		public static SuffixAutomatonOfBit build(char[] str)
		{
			int n = str.length;
			SuffixAutomatonOfBit sa = new SuffixAutomatonOfBit(n);
			sa.len = str.length;
			
			Node last = sa.t0;
			for(char c : str){
				last = sa.extend(last, c);
			}
			
			return sa;
		}
		
		public Node extend(Node last, char c)
		{
			Node cur = makeNode(last.len+1, null);
			Node p;
			for(p = last; p != null && !p.containsKeyNext(c);p = p.link){
				p.putNext(c, cur);
			}
			if(p == null){
				cur.link = t0;
			}else{
				Node q = p.getNext(c); // not null
				if(p.len + 1 == q.len){
					cur.link = q;
				}else{
					Node clone = makeNode(p.len+1, q);
					clone.next = Arrays.copyOf(q.next, q.next.length);
					clone.hit = q.hit;
					clone.np = q.np;
					clone.link = q.link;
					for(;p != null && q.equals(p.getNext(c)); p = p.link){
						p.putNext(c, clone);
					}
					q.link = cur.link = clone;
				}
			}
			return cur;
		}
		
		public SuffixAutomatonOfBit lexSort()
		{
			for(int i = 0;i < gen;i++){
				Node node = nodes[i];
				Arrays.sort(node.next, 0, node.np, new Comparator<Node>() {
					public int compare(Node a, Node b) {
						return a.key - b.key;
					}
				});
			}
			lexsorted = true;
			return this;
		}
		
		public SuffixAutomatonOfBit sortTopologically()
		{
			int[] indeg = new int[gen];
			for(int i = 0;i < gen;i++){
				for(int j = 0;j < nodes[i].np;j++){
					indeg[nodes[i].next[j].id]++;
				}
			}
			Node[] sorted = new Node[gen];
			sorted[0] = t0;
			int p = 1;
			for(int i = 0;i < gen;i++){
				Node cur = sorted[i];
				for(int j = 0;j < cur.np;j++){
					if(--indeg[cur.next[j].id] == 0){
						sorted[p++] = cur.next[j];
					}
				}
			}
			
			for(int i = 0;i < gen;i++)sorted[i].id = i;
			nodes = sorted;
			sortedTopologically = true;
			return this;
		}
		
		// visualizer
		
		public String toString()
		{
			StringBuilder sb = new StringBuilder();
			for(Node n : nodes){
				if(n != null){
					sb.append(String.format("{id:%d, len:%d, link:%d, cloned:%b, ",
							n.id,
							n.len,
							n.link != null ? n.link.id : null,
							n.original.id));
					sb.append("next:{");
					for(int i = 0;i < n.np;i++){
						sb.append(n.next[i].key + ":" + n.next[i].id + ",");
					}
					sb.append("}");
					sb.append("}");
					sb.append("\n");
				}
			}
			return sb.toString();
		}
		
		public String toGraphviz(boolean next, boolean suffixLink)
		{
			StringBuilder sb = new StringBuilder("http://chart.apis.google.com/chart?cht=gv:dot&chl=");
			sb.append("digraph{");
			for(Node n : nodes){
				if(n != null){
					if(suffixLink && n.link != null){
						sb.append(n.id)
						.append("->")
						.append(n.link.id)
						.append("[style=dashed],");
					}
					
					if(next && n.next != null){
						for(int i = 0;i < n.np;i++){
							sb.append(n.id)
							.append("->")
							.append(n.next[i].id)
							.append("[label=")
							.append(n.next[i].key)
							.append("],");
						}
					}
				}
			}
			sb.append("}");
			return sb.toString();
		}
		
		public String label(Node n)
		{
			if(n.original != null){
				return n.id + "C";
			}else{
				return n.id + "";
			}
		}
		
		public String toDot(boolean next, boolean suffixLink)
		{
			StringBuilder sb = new StringBuilder("digraph{\n");
			sb.append("graph[rankdir=LR];\n");
			sb.append("node[shape=circle];\n");
			for(Node n : nodes){
				if(n != null){
					if(suffixLink && n.link != null){
						sb.append("\"" + label(n) + "\"")
						.append("->")
						.append("\"" + label(n.link) + "\"")
						.append("[style=dashed];\n");
					}
					
					if(next && n.next != null){
						for(int i = 0;i < n.np;i++){
							sb.append("\"" + label(n) + "\"")
							.append("->")
							.append("\"" + label(n.next[i]) + "\"")
							.append("[label=\"")
							.append(n.next[i].key)
							.append("\"];\n");
						}
					}
				}
			}
			sb.append("}\n");
			return sb.toString();
		}
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new G2().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}


Leave a comment below

 

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionPseudo-Isomorphic Substrings – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMaking Candies – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAbsolute Element Sums – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAlmost Integer Rock Garden – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionPlus Minus – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMini-Max Sum – HackerRank Solution
Tags: Cc++14full solutionGoHackerRank SolutionHow Many Substrings?javajava 15java 7java 8java8javascriptpypy 3Python 2python 3
ShareTweetPin
bhautik bhalala

bhautik bhalala

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
29

Exclusive Time of Functions - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

Bike Racers - HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Task Scheduling - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionPseudo-Isomorphic Substrings – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMaking Candies – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAbsolute Element Sums – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAlmost Integer Rock Garden – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionPlus Minus – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMini-Max Sum – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
Biography

Sai Pallavi Net Worth, Age, Height , Achivements and more

September 8, 2022
1
Biography

Esha Gupta Net Worth, Age, Height , Achivements and more

September 8, 2022
0
Leetcode All Problems Solutions
Code Solutions

Beautiful Arrangement – LeetCode Solution

September 10, 2022
47
15 Days to learn SQL Hard SQL(Advanced)-Solution
Code Solutions

Japan Population EasySQL (Basic) – SQL – HackerRank Solution

May 30, 2022
0

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?