Supongamos que tenemos dos Strings: – Patrón y Texto
patrón: que consta de caracteres únicos
texto: que consta de cualquier longitud
Necesitamos encontrar la cantidad de patrones que se pueden obtener del texto eliminando todas y cada una de las ocurrencias de Patrón en el Texto.
Ejemplo :
Input : Pattern : ABC Text : ABABCABCC Output : 3 Occurrences found at: 4 7 8 Explanation Occurrences and their removal in the order 1. ABABCABCC 2. ABABCC 3. ABC
La idea es utilizar la estructura de datos de pila.
- Inicialice un puntero al comienzo para hacer coincidir las ocurrencias en el patrón con 0 y el contador a 0.
- Compruebe si el patrón y el texto tienen el mismo carácter en el índice actual.
- Si el puntero está al final del patrón, significa que todos los caracteres anteriores se han encontrado en un orden subsiguiente creciente, incremente el contador en 1.
- De lo contrario, siga incrementando el puntero en 1 si los caracteres son iguales.
- Si los caracteres son diferentes en ambas strings, verifique si el carácter es el mismo que el primer carácter del patrón (es decir, puntero = 0).
- 6. En caso afirmativo, agregue los caracteres restantes del puntero actual a la longitud del patrón a una pila y verifique si están presentes para que el patrón se pueda formar a partir de la pila. Además, inicialice el puntero ahora a 1 porque ya habíamos verificado el puntero = 0 (en el paso 5 ).
- Si coincide, vacía la pila a nulo . De lo contrario, elimine el primer carácter y siga agregando el resto de la substring para verificar los pasos posteriores.
- Si alguna string agregada a la pila coincide con el patrón, incremente el contador en 1 e inicialice el puntero en 0 .
- Repita todos estos pasos para todos los índices de la longitud del texto.
- Imprime el contador y las ocurrencias.
- La tarea básica de Stack es manejar las operaciones pendientes que podrían ser posibles ocurrencias.
Ejemplo de explicación según el algoritmo anterior :
TEXT: ABABCABCC PATTERN: ABC pointer = 0 counter = 0 A B A B C A B C C 0 1 2 3 4 5 6 7 8 at index = 0 pointer = 0 stack = [] at index = 1 pointer = 1 stack = [] at index = 2 pointer = 0 stack = ['C'] at index = 3 pointer = 1 stack = ['C'] at index = 4 pointer = 2 counter += 1 pointer = 0 stack = ['C'] same for index 5,6,7 according to above method at index = 8 pop from Stack counter += 1 clear Stack
Código en Java para el algoritmo :
Requisito previo: Clase de pila en Java
Implementación:
Java
import java.util.ArrayList;
import java.util.Stack;
class StackImplementation {
// custom class for returning multiple values
class Data {
ArrayList<Integer> present;
int count;
public Data(ArrayList<Integer> present, int count)
{
this.present = present;
this.count = count;
}
}
public Data Solution(char pattern[], char text[])
{
// stores the indices for all occurrences
ArrayList<Integer> list = new ArrayList<>();
Stack<String> stack = new Stack<>();
// present index pointer searched for in
// the entire array of string characters
int p = 0;
// count of all the number of occurrences
int counter = 0;
// any random number less than 0 to mark
// the previous index where the occurrence
// was found
int lastOccurrence = -10;
// traversing all the indexes of the text
// searching for possible pattern
for (int i = 0; i < text.length; i++) {
// if the present index and the pointer in
// the pattern is at same character
if (text[i] == pattern[p]) {
// and if that character is the end of
// the pattern to be found
if (text[i]
== pattern[pattern.length - 1]) {
// index at which pattern is found
list.add(i);
// incrementing total occurrences by 1
counter++;
// last found index to be initialized
// to present index
lastOccurrence = i;
// begin the search for the next pointer
// again from 0th index of the pattern
p = 0;
}
else {
// if present character at pattern and
// index is same but still not the end
// of pattern
p++;
}
}
// if characters are not same
else {
// if the present character is same as the
// 1st character of the pattern here 0 =
// pointer in the pattern fixed to 0
if (text[i] == pattern[0]) {
// assume a temporary string
String temp = "";
// and add all characters to it to the
// pattern length from the present
// pointer to the end
for (int i1 = p; i1 < pattern.length;
i1++)
temp += pattern[i1];
// push the present pattern length into
// the stack for checking if pattern is
// same as subsequence of the text
stack.push(temp);
// pattern at pointer = 0 already
// checked so we
// start from 1 for the next step
p = 1;
}
else {
// if the previous occurrence was just
// before the present index
if (lastOccurrence == i - 1) {
// if the stack is empty place the
// pointer = 0
if (stack.isEmpty())
p = 0;
else {
// pick up the present possible
// pattern
String temp = stack.pop();
// check if it's character has
// the matching occurrence
if (temp.charAt(0) == text[i]) {
// increment last index by
// the present index
// so that net index is
// checked
lastOccurrence = i;
// check if stack character
// is last character in the
// pattern
if (temp.charAt(0)
== pattern[pattern
.length
- 1]) {
// index found
list.add(i);
// increment occurrences
// by 1
counter++;
}
else {
// if present index
// character doesn't
// match the last
// character in the
// pattern remove the
// first character which
// was same and check
// for further
// occurrences of the
// remaining letters in
// the stack string
temp = temp.substring(
1, temp.length());
// add the remaining
// string back to stack
// for further review
stack.push(temp);
}
}
// if first string character in
// the stack doesn't match the
// present character in the text
else {
// if stack is not empty
// empty it.
if (!stack.isEmpty())
stack.clear();
// reinitialize the pointer
// back to 0 for checking
// pattern from beginning
p = 0;
}
}
}
else {
// empty the stack under any other
// circumstances
if (!stack.isEmpty())
stack.clear();
// reinitialize the pointer back to
// 0 for checking pattern from
// beginning
p = 0;
}
}
}
}
// return the result
return new Data(list, counter);
}
public static void main(String args[])
{
// the simple pattern to be matched
char[] pattern = "ABC".toCharArray();
// the input string in which the number of
// occurrences can be found out after removing
// each occurrence.
char[] text = "ABABCABCC".toCharArray();
StackImplementation obj = new StackImplementation();
Data data = obj.Solution(pattern, text);
int count = data.count;
ArrayList<Integer> list = data.present;
System.out.println(count);
if (count > 0) {
System.out.println("Occurrences found at:");
for (int i : list)
System.out.print(i + " ");
}
}
}
Producción
3 Occurrences found at: 4 7 8
Referencias :
1. Pila de documentación de Java.
2. Custom ArrayList y Class en Java.
3. Más sobre operaciones de pila.
Este artículo es una contribución de Shubham Saxena . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA