Dada una secuencia de paréntesis o, en otras palabras, una string S de longitud n, que consta de los caracteres ‘(‘ y ‘)’. Encuentre la longitud de la subsecuencia de corchete correcta máxima de la secuencia para un rango de consulta dado. Nota: Una secuencia de corchetes correcta es aquella que tiene pares de corchetes coincidentes o que contiene otra secuencia de corchetes correcta anidada. Por ejemplo,(), (()),()() son una secuencia de paréntesis correcta. Ejemplos:
Input : S = ())(())(())(
Start Index of Range = 0,
End Index of Range = 11
Output : 10
Explanation: Longest Correct Bracket Subsequence is ()(())(())
Input : S = ())(())(())(
Start Index of Range = 1,
End Index of Range = 2
Output : 0
Los árboles de segmentos se pueden usar para resolver este problema de manera eficiente . En cada Node del árbol de segmentos, almacenamos lo siguiente:
1) a - Number of correctly matched pairs of brackets. 2) b - Number of unused open brackets. 3) c - Number of unused closed brackets.
(Corchete abierto sin usar: significa que no se puede combinar con ningún corchete de cierre, corchete cerrado sin usar: significa que no se puede combinar con ningún corchete de apertura, por ejemplo, S = )( contiene un paréntesis abierto y cerrado sin usar) Para cada intervalo [L, R], podemos hacer coincidir X número de corchetes abiertos ‘(‘ en el intervalo [L, MID] con corchetes cerrados no utilizados ‘)’ en el intervalo [MID + 1, R] donde X = mínimo (número de no utilizados ‘(‘ en [L, MID], número de no utilizados ‘)’ en [MID + 1, R]) Por lo tanto, X es también el número de pares correctamente construidos por combinación. Entonces, para el intervalo [L, R] 1) El número total de pares coincidentes correctamente se convierte en la suma de los pares coincidentes correctos en el hijo izquierdo y los pares coincidentes correctos en el hijo derecho y el número de combinaciones de ‘(‘ y ‘)’ no utilizados de la izquierda e hijo derecho respectivamente.
a[L, R] = a[L, MID] + a[MID + 1, R] + X
2) El número total de corchetes abiertos no utilizados se convierte en la suma de los corchetes abiertos no utilizados en el elemento secundario izquierdo y los corchetes abiertos no utilizados en el elemento secundario derecho menos X (menos, porque usamos X no utilizados ‘(‘ del elemento secundario izquierdo para coincidir con los elementos no utilizados ‘) del elemento secundario derecho ).
a[L, R] = b[L, MID] + b[MID + 1, R] - X
3) De manera similar, para corchetes cerrados no utilizados, se mantiene la siguiente relación.
a[L, R] = c[L, MID] + c[MID + 1, R] - X
donde a, b y c son las representaciones descritas anteriormente para cada Node en el que se almacenará. A continuación se muestra la implementación del enfoque anterior en C++.
CPP
/* CPP Program to find the longest correct
bracket subsequence in a given range */
#include <bits/stdc++.h>
using namespace std;
/* Declaring Structure for storing
three values in each segment tree node */
struct Node {
int pairs;
int open; // unused
int closed; // unused
Node()
{
pairs = open = closed = 0;
}
};
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e - s) / 2; }
// Returns Parent Node after merging its left and right child
Node merge(Node leftChild, Node rightChild)
{
Node parentNode;
int minMatched = min(leftChild.open, rightChild.closed);
parentNode.pairs = leftChild.pairs + rightChild.pairs + minMatched;
parentNode.open = leftChild.open + rightChild.open - minMatched;
parentNode.closed = leftChild.closed + rightChild.closed - minMatched;
return parentNode;
}
// A recursive function that constructs Segment Tree
// for string[ss..se]. si is index of current node in
// segment tree st
void constructSTUtil(char str[], int ss, int se, Node* st,
int si)
{
// If there is one element in string, store it in
// current node of segment tree and return
if (ss == se) {
// since it contains one element, pairs
// will be zero
st[si].pairs = 0;
// check whether that one element is opening
// bracket or not
st[si].open = (str[ss] == '(' ? 1 : 0);
// check whether that one element is closing
// bracket or not
st[si].closed = (str[ss] == ')' ? 1 : 0);
return;
}
// If there are more than one elements, then recur
// for left and right subtrees and store the relation
// of values in this node
int mid = getMid(ss, se);
constructSTUtil(str, ss, mid, st, si * 2 + 1);
constructSTUtil(str, mid + 1, se, st, si * 2 + 2);
// Merge left and right child into the Parent Node
st[si] = merge(st[si * 2 + 1], st[si * 2 + 2]);
}
/* Function to construct segment tree from given
string. This function allocates memory for segment
tree and calls constructSTUtil() to fill the
allocated memory */
Node* constructST(char str[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Declaring array of structure Allocate memory
Node* st = new Node[max_size];
// Fill the allocated memory st
constructSTUtil(str, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
/* A Recursive function to get the desired
Maximum Sum Sub-Array,
The following are parameters of the function-
st --> Pointer to segment tree
si --> Index of the segment tree Node
ss & se --> Starting and ending indexes of the
segment represented by
current Node, i.e., tree[index]
qs & qe --> Starting and ending indexes of query range */
Node queryUtil(Node* st, int ss, int se, int qs,
int qe, int si)
{
// No overlap
if (ss > qe || se < qs) {
// returns a Node for out of bounds condition
Node nullNode;
return nullNode;
}
// Complete overlap
if (ss >= qs && se <= qe) {
return st[si];
}
// Partial Overlap Merge results of Left
// and Right subtrees
int mid = getMid(ss, se);
Node left = queryUtil(st, ss, mid, qs, qe, si * 2 + 1);
Node right = queryUtil(st, mid + 1, se, qs, qe, si * 2 + 2);
// merge left and right subtree query results
Node res = merge(left, right);
return res;
}
/* Returns the maximum length correct bracket
subsequencebetween start and end
It mainly uses queryUtil(). */
int query(Node* st, int qs, int qe, int n)
{
Node res = queryUtil(st, 0, n - 1, qs, qe, 0);
// since we are storing numbers pairs
// and have to return maximum length, hence
// multiply no of pairs by 2
return 2 * res.pairs;
}
// Driver Code
int main()
{
char str[] = "())(())(())(";
int n = strlen(str);
// Build segment tree from given string
Node* st = constructST(str, n);
int startIndex = 0, endIndex = 11;
cout << "Maximum Length Correct Bracket"
" Subsequence between "
<< startIndex << " and " << endIndex << " = "
<< query(st, startIndex, endIndex, n) << endl;
startIndex = 1, endIndex = 2;
cout << "Maximum Length Correct Bracket"
" Subsequence between "
<< startIndex << " and " << endIndex << " = "
<< query(st, startIndex, endIndex, n) << endl;
return 0;
}
Maximum Length Correct Bracket Subsequence between 0 and 11 = 10 Maximum Length Correct Bracket Subsequence between 1 and 2 = 0
La complejidad del tiempo para cada consulta es O(logN) , donde N es el tamaño de la string.
Espacio Auxiliar: O(N)
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA