पायथन में दिए गए स्ट्रिंग्स के सबस्ट्रिंग्स को सभी संभावित सबस्ट्रिंग्स के सेट में दिए गए स्थानों पर खोजने का प्रोग्राम

मान लीजिए हमें n संख्या में स्ट्रिंग्स दी गई हैं; str1, str2, str3,.....,strn। अब, मान लीजिए कि substr_i एक सेट है जिसमें str_i के सभी सबस्ट्रिंग्स हैं। सभी सबस्ट्र सेट्स का यूनियन substr_union है। अब हमें q संख्या में क्वेरीज दी गई हैं, और हमें substr_union के q-th तत्व को ढूंढना है। सेट substr_union लेक्सिकोग्राफिकली सॉर्टेड है और इंडेक्स 1 से शुरू होते हैं।

उदाहरण के लिए, यदि स्ट्रिंग्स की सूची = ['pqr', 'pqt'] है, क्वेरीज = [4, 7, 9], तो आउटपुट ['pqt', 'qt', 't'] होगा।

पहली स्ट्रिंग से सबस्ट्रिंग्स हैं subs_str_1 = {p, pq, pqr, q, qr, r}, sub_str_2 = {p, pq, pqt, q, qt, t}।

इन दो सेट्स का यूनियन, या substr_union है {p, pq, pqr, pqt, q, qr, qt, r, t}।

तो इंडेक्स 4, 7, और 9 पर आइटम्स 'pqt', 'qt', और 't' हैं।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

lng_i() नामक एक फंक्शन परिभाषित करें। यह suff, lng, i लेगा
- d := (suff, lng) वाला एक नया टपल
- lo := 0
- hi := 0
- d में प्रत्येक टपल (suf, lng) के लिए, करें
  - यदि lng, null के समान है, तो
    - lng := 0
  - hi := hi + suf का आकार - lng
  - यदि hi - 1, i के समान है, तो
    - suf लौटाएं
  - अन्यथा जब hi - 1 > i, तो
    - इंडेक्स p और आइटम q के लिए lng से suf के आकार तक की मानों की सूची में, करें
      - यदि lo + p, i के समान है, तो
        suf[इंडेक्स 0 से j+1 तक] लौटाएं
  - lo := hi
- False लौटाएं
hlp_ii() नामक एक फंक्शन परिभाषित करें। यह str1, str2 लेगा
- ub := str1 के आकार, str2 के आकार का न्यूनतम
- cnt := 0
- i के लिए 0 से ub तक की रेंज में, करें
  - यदि str1[i], str2[i] के समान है, तो
    - cnt := cnt + 1
  - अन्यथा,
    - cnt लौटाएं
  - cnt लौटाएं
t_dict := एक नया मैप
suff := एक नई सूची
lng := एक नई सूची
strings में प्रत्येक str के लिए, करें
- i के लिए 0 से str के आकार तक की रेंज में, करें
  - value := str[इंडेक्स i से अंत तक]
  - यदि value, t_dict में मौजूद नहीं है, तो
    - t_dict[value] := 1
    - value को suff के अंत में डालें
suff सूची को सॉर्ट करें
suff_len := suff का आकार
i के लिए 0 से suff_len के आकार तक की रेंज में, करें
- यदि i, 0 के समान है, तो
  - null को lng के अंत में डालें
- अन्यथा,
  - hlp_ii(suff[i-1], suff[i]) को lng के अंत में डालें
res := एक नई सूची
q_list में प्रत्येक q के लिए, करें
- (lng_i(suff, lng, q-1)) को res के अंत में डालें
res लौटाएं

उदाहरण

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

def lng_i(suff, lng, i):
    d = zip(suff, lng)
    lo = hi = 0
    for suf, lng in d:
        if lng is None:
            lng = 0
        hi += len(suf) - lng
        if hi - 1 == i:
            return suf
        elif hi - 1 > i:
            for p, q in enumerate(list(range(lng, len(suf)))):
                if lo + p == i:
                    return suf[:q+1]
        lo = hi
    return False

def hlp_ii(str1, str2):
    ub = min(len(str1), len(str2))
    cnt = 0
    for i in range(ub):
        if str1[i] == str2[i]:
            cnt += 1
        else:
            return cnt
    return cnt

def solve(strings, q_list):
    t_dict = {}
    suff = []
    lng = []
    for str in strings:
        for i in range(len(str)):
            value = str[i:]
            if value not in t_dict:
                t_dict[value] = 1
                suff.append(value)
    suff.sort()
    suff_len = len(suff)
    for i in range(suff_len):
        if i == 0:
            lng.append(None)
        else:
            lng.append(hlp_ii(suff[i-1], suff[i]))
    res = []
    for q in q_list:
        res.append(lng_i(suff, lng, q-1))
    return res

print(solve(['pqr', 'pqt'], [4, 7, 9]))

इनपुट

['pqr', 'pqt'], [4, 7, 9]

आउटपुट

['pqt', 'qt', 't']