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

मान लीजिए कि हमें स्ट्रिंग्स की संख्या प्रदान की जाती है; str1, str2, str3,......,strn. अब, मान लीजिए कि सबस्ट्री एक सेट है जिसमें स्ट्री के सभी सबस्ट्रिंग शामिल हैं। सभी सबस्ट्र सेटों का मिलन substr_union है। अब हमें प्रश्नों की q संख्या दी गई है, और हमें सेट substr_union के q-वें तत्व को खोजना होगा। सेट 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() । यह पर्याप्त होगा, lng, i
- d :=एक नया टपल युक्त (suff, lng)
- लो :=0
- नमस्ते:=0
- d में प्रत्येक टपल (suf, lng) के लिए, do
  - यदि lng शून्य के समान है, तो
    - एलएनजी:=0
  - नमस्ते:=हाय + सूफ का आकार - एलएनजी
  - यदि hi-1, i के समान है, तो
    - रिटर्न सूफ
  - अन्यथा जब hi-1> i, तब
    - इंडेक्स p और आइटम q के लिए lng से suf के आकार के मानों की सूची में, करें
      - यदि lo + p, i के समान है, तो
        
        सुफ लौटाएं[सूचकांक 0 से j+1 तक]
  - लो:=हाय
- झूठी वापसी
एक फ़ंक्शन परिभाषित करें hlp_ii() । इसमें str1,str2
- ub :=न्यूनतम आकार का str1 , str2 का आकार
- सीएनटी:=0
- 0 से लेकर ub तक के i के लिए, करें
  - अगर str1[i] str2[i] के समान है, तो
    - सीएनटी:=सीएनटी + 1
  - अन्यथा,
    - वापसी सीएनटी
  - वापसी सीएनटी
t_dict :=एक नया नक्शा
सफ़:=एक नई सूची
lng :=एक नई सूची
स्ट्रिंग्स में प्रत्येक स्ट्र के लिए, करें
- मैं के लिए 0 से लेकर स्ट्र के आकार की सीमा में, ऐसा करें
  - मान :=str[सूचकांक i से अंत तक]
  - यदि मान t_dict में मौजूद नहीं है, तो
    - t_dict[value] :=1
    - सफ़ के अंत में मान डालें
सूची को पर्याप्त क्रमित करें
suff_len :=प्रत्यय का आकार
मैं के लिए 0 से suff_len के आकार की सीमा में, करते हैं
- यदि मैं 0 के समान है, तो
  - एलएनजी के अंत में शून्य डालें
- अन्यथा,
  - lng के अंत में hlp_ii(suff[i-1], suff[i]) डालें
res :=एक नई सूची
q_सूची में प्रत्येक q के लिए, करें
- रेस के अंत में (lng_i(suff, lng, q-1)) डालें
रिटर्न रेस

उदाहरण

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

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']