पायथन में स्टैम्पिंग अनुक्रम के लिए इंडेक्स खोजने का प्रोग्राम

मान लीजिए हम लोअरकेस अक्षरों का एक टारगेट स्ट्रिंग बनाना चाहते हैं। पहले, हमारे पास n '?' मार्क्स का अनुक्रम होता है (n टारगेट स्ट्रिंग की लंबाई है)। हमारे पास लोअरकेस अक्षरों का एक स्टैम्प भी होता है। प्रत्येक चाल में, हम अनुक्रम पर स्टैम्प रख सकते हैं, और उसमें हर अक्षर को स्टैम्प से संबंधित अक्षर से बदल सकते हैं। आप 10 * n चाल तक बना सकते हैं।

उदाहरण के लिए, प्रारंभिक अनुक्रम "?????" पर विचार करें, और स्टैम्प "abc" है, तो हम पहले चाल में "abc??", "?abc?", "??abc" जैसी स्ट्रिंग्स बना सकते हैं। यदि अनुक्रम को स्टैम्प करना संभव है, तो प्रत्येक चाल में स्टैम्प किए गए सबसे बाएं अक्षर के इंडेक्स का एक ऐरे वापस करें। यदि यह संभव नहीं है तो एक खाली ऐरे वापस करें। इसलिए जब अनुक्रम "ababc" है, और स्टैम्प "abc" है, तो उत्तर [0, 2] जैसा हो सकता है, क्योंकि हम "?????" -> "abc??" -> "ababc" बना सकते हैं।

उदाहरण के लिए, यदि इनपुट s = "abcd", t = "abcdbcd" है, तो आउटपुट [3,0] होगा।

हल करने के चरण

1. यदि len(s) == 1, तो:
   • यदि t के सभी कैरेक्टर समान हैं और वे s[0] हैं, तो 0 से len(t) तक की सूची वापस करें, अन्यथा खाली सूची।
2. ans := एक नई सूची
3. t len(t) संख्या के "?" मार्क्स के बराबर न होने तक व्हाइल लूप चलाएं:
   • tmp := t
   • i को 0 से len(s) तक लूप चलाएं:
     • j को len(s) से i+1 तक घटाते हुए लूप चलाएं:
       • search := i संख्या के "?" + s[i:j] सबस्ट्रिंग + (len(s)-j) संख्या के "?"
       • search t में होने तक व्हाइल लूप चलाएं:
         • t.find(search) को ans के अंत में जोड़ें
         • t := t.replace(search, "?"*len(s), 1) केवल एक बार बदलें
       • यदि t == "?" * len(t), तो लूप से बाहर निकलें
     • यदि t == "?" * len(t), तो लूप से बाहर निकलें
   • यदि tmp == t, तो लूप से बाहर निकलें
4. ans का उल्टा वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(s, t):
    if len(s) == 1:
        return [i for i in range(len(t))] if all(ch == s[0] for ch in t) else []
    ans = []
    while t != "?" * len(t):
        tmp = t
        for i in range(len(s)):
            for j in reversed(range(i+1, len(s)+1)):
                search = "?" * i + s[i:j] + "?" * (len(s)-j)
                while t.find(search) != -1:
                    ans.append(t.find(search))
                    t = t.replace(search, "?"*len(s), 1)
                if t == "?" * len(t):
                    break
            if t == "?" * len(t):
                break
        if tmp == t:
            return []
    return ans[::-1]

s = "abcd"
t = "abcdbcd"
print(solve(s, t))

इनपुट

"abcd", "abcdbcd"

आउटपुट

[3,0]