تكرارات النمط باستخدام المكدس


مستوى الصعوبة متوسط
لارسن وتوبرو كومة خيط

المشكلة بيان

إعطاء صفيفين نمط [] ونص [] من حرف يكتب. تطلب مشكلة "تكرار النمط باستخدام المكدس" إنشاء وظيفة للعثور على العدد الإجمالي لتكرارات النمط في النص أثناء إزالة النمط الموجود من النص باستخدام بنية بيانات المكدس.

تكرارات النمط باستخدام المكدس

مثال

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 و -XNUMX على التوالي.
  5. الانتقال من 0 إلى حجم مصفوفة النص - 1.
  6. تحقق مما إذا كانت القيمة الموجودة في الفهرس الحالي لمصفوفة النص تساوي القيمة الموجودة في الفهرس p في مصفوفة النمط. إذا كانت القيمة الموجودة في الفهرس الحالي لمصفوفة النص تساوي القيمة الموجودة في حجم الفهرس - 1 في مصفوفة النمط ، فاضغط / أدخل الفهرس الحالي في المتجه. قم بزيادة العداد بمقدار 1. قم بتحديث قيم lastOccurrence و p كـ 1 و 0 على التوالي. عدا ذلك ، قم بزيادة p بمقدار 1.
  7. تحقق أيضًا مما إذا كانت القيمة في الفهرس الحالي لمصفوفة النص تساوي القيمة الموجودة في الفهرس الأول في مصفوفة النمط ، قم بإنشاء متغير سلسلة مؤقت. قم بالانتقال من p إلى حجم صفيف النمط وإضافة الحرف في الفهرس الحالي في متغير السلسلة. ادفع متغير السلسلة المؤقتة في المكدس وقم بتحديث قيمة p كـ 1.
  8. تحقق آخر مما إذا كانت lastOccurrence تساوي الفهرس الحالي - 1 ، إذا كان المكدس فارغًا التحديث p مثل 0.
  9. عدا ذلك ، قم بإنشاء متغير سلسلة مؤقت وافتح الجزء العلوي من المكدس وتخزينه في السلسلة التي تم إنشاؤها حديثًا. إذا كان الحرف الأول من السلسلة يساوي القيمة الموجودة في الفهرس الحالي في المصفوفة النصية ، فقم بتحديث lastOccurence على أنه الفهرس الحالي.
  10. إذا كان الحرف الأول من سلسلة تساوي القيمة عند حجم المؤشر - 1 في مصفوفة النمط ، ادفع الفهرس الحالي في المتجه وزد العداد بمقدار 1. وإلا ادفع السلسلة في كومة.
  11. عدا ذلك ، إذا لم تكن المكدس فارغة ، فقم بتنظيفها واضبط p على 0.
  12. اطبع العداد وقائمة المتجهات.

رمز

برنامج C ++ لأحداث النمط باستخدام 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 لأحداث النمط باستخدام 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

تحليل التعقيد

تعقيد الوقت

O (ts) حيث ts هو عدد الأحرف في نص مصفوفة الأحرف [].

تعقيد الفضاء

O (ts) لأننا استخدمنا مساحة لتخزين الأحرف.