Stack қолданатын өрнектер


Күрделілік дәрежесі орта
Ларсен және Тубро үйме String

Проблемалық мәлімдеме

Екі массивтің өрнегі [] және мәтіні [] берілген кейіпкер түрі. «Стектің көмегімен өрнектің пайда болуы» мәселесі стек деректер құрылымын қолданып, табылған үлгіні мәтіннен алып тастағанда, мәтіндегі өрнектің жалпы санын табу функциясын құруды сұрайды.

Stack қолданатын өрнектер

мысал

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

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

Occurrences found at:
4 7 8

Түсініктеме: Сіз үш паттерді тексеру үшін жоғарыдағы суретті көре аласыз

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

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

Stack көмегімен өрнектің пайда болу алгоритмі

  1. Екі инициализация массивтер өрнек [] және мәтін [] кейіпкер түрі.
  2. Параметр ретінде екі таңбалық массивті қабылдайтын өрнектің пайда болуын табу функциясын жасаңыз.
  3. Бүтін типтегі векторды және жол типіндегі стек деректер құрылымын жасаңыз.
  4. Осыдан кейін p, counter және lastOccurrence үш бүтін айнымалыларын құрыңыз және оларды сәйкесінше 0,0 және -10 деп инициализациялаңыз.
  5. Мәтіндік массивтің өлшемінен 0-ге дейін - 1.
  6. Мәтіндік массивтің ағымдағы индексіндегі мән үлгі массивіндегі р индексіндегі мәнге тең екендігін тексеріңіз. Егер мәтіндік массивтің ағымдағы индексіндегі мән индекс өлшеміндегі мәнге тең болса - өрнек массивінде 1, векторға ағымдық индексті итеріңіз / салыңыз. Есептегішті 1-ге көбейтіңіз, lastOccurrence және p мәндерін сәйкесінше 1 және 0 етіп жаңартыңыз. Басқасы р-ны 1-ге көбейтеді.
  7. Мәтіндік массивтің ағымдық индексіндегі мән үлгі массивіндегі бірінші индекстегі мәнге тең екендігін тағы бір тексеріп, уақытша жолдық айнымалы жасаңыз. Р-дан массив өлшеміне дейін өтіңіз және символды жолдың айнымалысына ағымдық индекске қосыңыз. Уақытша жол айнымалысын стекке итеріп, p мәнін 1 ретінде жаңартыңыз.
  8. Егер lastOccurrence ағымдағы индекске тең болса, тағы біреуін тексеріңіз, егер стек бос жаңарту болса, 1.
  9. Басқасы уақытша жол айнымалысын жасайды және стектің жоғарғы жағын ашып, жаңадан жасалған жолда сақтайды. Егер жолдың бірінші таңбасы мәтіндік массивтегі ағымдағы индекстегі мәнге тең болса, lastOccurence-ді ағымдағы индекс ретінде жаңартыңыз.
  10. Егер бірінші символ жол индекс өлшеміндегі мәнге тең - өрнек массивінде 1, ағымдық индексті векторға итеріп, есептегішті 1-ге көбейтіңіз. Стек.
  11. Егер стек бос болмаса, стекті тазалап, p мәнін 0 деп қойыңыз.
  12. Есептегішті және векторлық тізімді басып шығарыңыз.

код

Stack қолданатын өрнектерге арналған 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-ті қолданатын шаблондық оқиғаларға арналған 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

Күрделілікті талдау

Уақыттың күрделілігі

O (ts), мұндағы ts - символдар массивінің таңбаларының саны [].

Ғарыштың күрделілігі

O (ts), өйткені біз таңбаларды сақтау үшін кеңістікті пайдаландық.