Table of Contents
Problem Statement
Given two arrays pattern[ ] and text[ ] of character type. The problem “Pattern Occurrences using Stack” asks to create a function to find the total number of occurrences of the pattern in the text while removing the found pattern from the text using the stack data structure.
Example
pattern[ ] = {'A','B','C'}
text[ ] = {'A','B','A','B','C','A','B','C','C'}3 Occurrences found at: 4 7 8
Explanation: You can see the image above to check the three patters
pattern[ ] : {'H','I'}
text[ ] : {'H','I','H','H','I','I','H','I'}4 Occurrences found at: 1 4 5 7
Algorithm for Pattern Occurrences using Stack
- Initialize two arrays pattern[ ] and text[ ] of character type.
- Create a function to find pattern occurrence which accepts two character arrays as it’s parameter.
- Create a vector of integer type and a stack data structure of string type.
- After that, create three integer variables p, counter, and lastOccurrence and initialize them as 0,0 and -10 respectively.
- Traverse from 0 to size of text array – 1.
- Check if the value at the current index of the text array is equal to the value at index p in pattern array. If the value at current index of the text array is equal to the value at index size – 1 in pattern array, push/insert the current index in the vector. Increment the counter by 1. Update the values of lastOccurrence and p as 1 and 0 respectively. Else increment the p by 1.
- Else check if the value at the current index of the text array is equal to the value at the first index in pattern array, create a temporary string variable. Traverse from p to size of pattern array and add the character at the current index in the string variable. Push the temporary string variable in the stack and update the value of p as 1.
- Else check if lastOccurrence is equal to current index – 1, if stack is empty update p as 0.
- Else create a temporary string variable and pop the top of the stack and store in the newly created string. If the first character of string is equal to the value at the current index in the text array, update the lastOccurence as the current index.
- If the first character of the string is equal to the value at index size – 1 in pattern array, push the current index in vector and increment the counter by 1. Else push the string in the stack.
- Else if the stack is not empty clean the stack and set p as 0.
- Print the counter and the vector list.
Code
C++ Program for Pattern Occurrences using Stack
#include<bits/stdc++.h>
using namespace std;
void PatternOccurence(char pattern[], char text[], int ps, int ts){
vector<int> list;
stack<string> st;
int p = 0;
int counter = 0 ;
int lastOccurrence = -10;
for(int i = 0; i < ts; i ++){
if(text[i] == pattern[p]){
if(text[i] == pattern[ps - 1]){
list.push_back(i);
counter ++;
lastOccurrence = i;
p = 0;
}
else{
p ++;
}
}
else{
if(text[i] == pattern[0]){
string temp = "";
for (int i1 = p; i1 < ps; i1 ++){
temp += pattern[i1];
}
st.push(temp);
p = 1;
}
else{
if(lastOccurrence == i - 1){
if(st.empty()){
p = 0;
}
else{
string temp = st.top();
st.pop();
if(temp[0] == text[i]){
lastOccurrence = i;
if(temp[0] == pattern[ps - 1]){
list.push_back(i);
counter ++;
}
else{
temp = temp.substr(1, temp.length());
st.push(temp);
}
}
else{
if(!st.empty())
while(!st.empty()){
st.pop();
}
p = 0;
}
}
}
else{
if (!st.empty()){
while(!st.empty()){
st.pop();
}
}
p = 0;
}
}
}
}
cout<<counter<<endl;
if(counter>0){
cout<<"Occurrences found at:"<<endl;
for(auto i = list.begin(); i != list.end(); ++i){
cout << *i << " ";
}
}
}
int main(){
char pattern[] = {'A','B','C'};
char text[] = {'A','B','A','B','C','A','B','C','C'};
int ps = sizeof(pattern)/sizeof(pattern[0]);
int ts = sizeof(text)/sizeof(text[0]);
PatternOccurence(pattern, text, ps, ts);
return 0;
}3 Occurrences found at: 4 7 8
Java Program for Pattern Occurrences using Stack
import java.util.ArrayList;
import java.util.Stack;
class StackImplementation{
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[]){
ArrayList<Integer> list = new ArrayList<>();
Stack<String> stack = new Stack<>();
int p = 0;
int counter = 0 ;
int lastOccurrence = -10;
for(int i = 0; i < text.length; i ++){
if(text[i] == pattern[p]){
if(text[i] == pattern[pattern.length - 1]){
list.add(i);
counter ++;
lastOccurrence = i;
p = 0;
}
else{
p ++;
}
}
else{
if(text[i] == pattern[0]){
String temp = "";
for (int i1 = p; i1 < pattern.length; i1 ++){
temp += pattern[i1];
}
stack.push(temp);
p = 1;
}
else{
if(lastOccurrence == i - 1){
if(stack.isEmpty()){
p = 0;
}
else{
String temp = stack.pop();
if (temp.charAt(0) == text[i]){
lastOccurrence = i;
if(temp.charAt(0) == pattern[pattern.length - 1]){
list.add(i);
counter ++;
}
else{
temp = temp.substring(1, temp.length());
stack.push(temp);
}
}
else{
if (!stack.isEmpty())
stack.clear();
p = 0;
}
}
}
else{
if (!stack.isEmpty()){
stack.clear();
}
p = 0;
}
}
}
}
return new Data(list, counter);
}
public static void main(String args[]){
char[] pattern = "ABC".toCharArray();
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 + " ");
}
}
}
}3 Occurrences found at: 4 7 8
Complexity Analysis
Time Complexity
O(ts) where ts is the number of characters in character array text[ ].
Space Complexity
O(ts) because we used space to store characters.