Stack ကို အသုံးပြု၍ Pattern ဖြစ်ပျက်မှု


ခက်ခဲအဆင့် အလယ်အလတ်
Larsen & Toubro စုပုံထား ကြိုး

ပြProbleနာဖော်ပြချက်

နှစ်ခု Array ကိုပုံစံ [] နှင့်စာသား [] ပေးထားသည် ဇာတ်ကောင် အမျိုးအစား။ အဆိုပါပြ “နာ "Pattern ကို Occurrences ကိုသုံးပြီး Stack" stack ဒေတာဖွဲ့စည်းပုံကိုအသုံးပြု။ စာသားကနေတွေ့ရှိခဲ့ပုံစံဖယ်ရှားပစ်နေစဉ်စာသားထဲမှာပုံစံ၏ဖြစ်ပွားမှုစုစုပေါင်းအရေအတွက်ကိုရှာဖွေတဲ့ function ကိုဖန်တီးရန်မေးတယ်။

Stack ကို အသုံးပြု၍ Pattern ဖြစ်ပျက်မှု

နမူနာ

pattern[ ] = {'A','B','C'}

text[ ] = {'A','B','A','B','C','A','B','C','C'}
3

Occurrences found at:
4 7 8

ရှင်းလင်းချက် - patters သုံးခုကိုစစ်ဆေးရန်အထက်ပါပုံကိုသင်ကြည့်နိုင်သည်

pattern[ ] : {'H','I'}

text[ ] : {'H','I','H','H','I','I','H','I'}
4
Occurrences found at:
1 4 5 7

Stack ကိုသုံးပြီး Pattern ဖြစ်ပျက်မှုအတွက် Algorithm

  1. နှစ်ခုစတင်ပါ Array များ ပုံစံ [] နှင့်စာသား [] ဇာတ်ကောင် အမျိုးအစား။
  2. ၎င်းသည် parameter အဖြစ်အရစာလုံးနှစ်လုံးကိုလက်ခံသောပုံစံဖြစ်ပျက်မှုကိုရှာဖွေရန် function တစ်ခုကိုဖန်တီးပါ။
  3. integer အမျိုးအစား vector နှင့် string type stack data structure ကိုဖန်တီးပါ။
  4. ပြီးရင် p, counter, နဲ့ lastOccurrence ကိန်းနှစ်ခုသုံးခုကိုဖန်တီးပြီးသူတို့ကို 0,0 နဲ့ -10 အဖြစ်အသီးသီးစလိုက်ပါ။
  5. 0 မှစာသားခင်းကျင်း၏အရွယ်အစားသို့လမ်းကြောင်း - 1 ။
  6. စာသားခင်းကျင်းမှု၏လက်ရှိအညွှန်းကိန်းရှိတန်ဖိုးသည်ပုံစံခင်းကျင်းမှုရှိအညွှန်း (p) တန်ဖိုးနှင့်တန်းတူမဟုတ်ကိုစစ်ဆေးပါ။ စာသားခင်းကျင်းမှု၏လက်ရှိအညွှန်းကိန်းရှိတန်ဖိုးသည်အညွှန်းအရွယ်အစားရှိတန်ဖိုးနှင့်တန်းတူပါက ၁။ ပုံစံခင်းကျင်းခြင်းတွင် ၁၊ အားနည်းချက်ကိုလက်ရှိအညွှန်းတွင်တွန်းထည့်ပါ။ ကောင်တာကို lastOccurrence နှင့် p ၏တန်ဖိုးများကို 1 နှင့် 1 အဖြစ်ပြောင်းပေးပါ။ ကျန်သည် 1 ကို p တိုးချဲ့သည်။
  7. အခြားစာသားခင်းကျင်းမှု၏လက်ရှိအညွှန်းကိန်းတန်ဖိုးသည်ပုံစံခင်းကျင်းမှုအတွင်းရှိပထမဆုံးအညွှန်းကိန်းတန်ဖိုးနှင့်ညီမျှမှုရှိမရှိစစ်ဆေးပါ၊ ယာယီစာသား variable ကိုဖန်တီးပါ။ p မှပုံစံခင်းကျင်းခြင်းအရွယ်သို့လမ်းကြောင်းပြောင်း။ string variable ထဲရှိလက်ရှိအညွှန်းတွင်ထည့်ပါ။ stack ထဲတွင်ယာယီ string variable ကိုတွန်းနှင့် p ၏တန်ဖိုး 1 အဖြစ်ကို update ။
  8. နောက်တစ်ခုက lastOccurrence သည်လက်ရှိအညွှန်း - 1 ဟုတ်မဟုတ်စစ်ဆေးသည်။
  9. ကျန်သည်ယာယီ string variable ကိုဖန်တီးပြီးအသစ်ဖန်တီးထားသော string တွင် stack နှင့် store ၏ထိပ်ကိုပေါ်လာပါ။ string ၏ပထမဆုံးဇာတ်ကောင်သည် text array ရှိလက်ရှိအညွှန်းကိန်းတန်ဖိုးနှင့်တူညီပါက lastOccurence ကိုလက်ရှိအညွှန်းအဖြစ် update လုပ်ပါ။
  10. ၏ပထမဇာတ်ကောင်ပါ ကြိုး index array ၏တန်ဖိုးနှင့်ညီမျှသည်။ ပုံစံခင်းကျင်းခြင်းတွင် ၁၊ လက်ရှိအညွှန်းကို vector နှင့်တွန်းပြီးကောင်တာကို ၁ တိုးခြင်းဖြင့်တိုးခြင်းဖြစ်သည်။ စုပုံထား.
  11. ကျန်သည် stack အချည်းနှီးမဖြစ်လျှင် stack ကိုရှင်းလင်းပြီး p အဖြစ် 0 ထားပါ။
  12. ကောင်တာနှင့်အားနည်းချက်ကိုစာရင်းပုံနှိပ်ပါ။

ကုဒ်

Stack ကို သုံး၍ Pattern Occurrences အတွက် C ++ အစီအစဉ်

#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

Stack ကို သုံး၍ Pattern Occurrences အတွက် Java အစီအစဉ်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (ts) ။ ts သည်အက္ခရာခင်းကျင်းစာသားရှိစာလုံးအရေအတွက် [] ။

အာကာသရှုပ်ထွေးမှု

အို (ts) ဘာကြောင့်လဲဆိုတော့စာလုံးတွေကိုသိမ်းဖို့နေရာလွတ်ကိုသုံးတယ်။