मान लीजिए कि हमारे पास दो स्ट्रिंग्स s1 और s2 हैं, हमें s1 में सबसे छोटा सबस्ट्रिंग ढूंढना होगा ताकि s2 के सभी कैरेक्टर कुशलतापूर्वक उपयोग किए जा सकें।
इसलिए, यदि इनपुट s1 ="मैं एक छात्र हूँ", s2 ="mdn" जैसा है, तो आउटपुट "m a स्टूडेन" होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एन:=26
-
str_len:=main_str का आकार, patt_len:=पैटर्न का आकार
-
अगर str_len
-
कोई नहीं लौटाएं
-
-
हैश_पैट:=आकार एन की एक सरणी और 0 से भरें
-
हैश_स्ट्र:=आकार एन की एक सरणी और 0 से भरें
-
मेरे लिए 0 से patt_len की सीमा में, करें
-
हैश_पैट [एएससीआईआई (पैटर्न [i])]:=हैश_पैट [एएससीआईआई (पैटर्न [i])] + 1
-
-
प्रारंभ:=0, start_index:=-1, min_len:=inf
-
गिनती :=0
-
j के लिए 0 से str_len की श्रेणी में, करें
-
हैश_स्ट्र [एएससीआईआई (मेन_स्ट्र [जे])]:=हैश_स्ट्र [एएससीआईआई (मेन_स्ट्र [जे])] + 1
-
अगर hash_pat[ASCII of(main_str[j]) ] 0 और hash_str[ASCII of(main_str[j]) ] <=hash_pat[ASCII of(main_str[j]) ] के समान नहीं है, तो
-
गिनती :=गिनती + 1
-
-
अगर गिनती patt_len के समान है, तो
-
जबकि hash_str[ASCII of(main_str[start]) ]> hash_pat[ASCII of(main_str[start])] या hash_pat[ASCII of(main_str[start])] 0 के समान है, do
-
अगर हैश_स्ट्र[ASCII of(main_str[start])]> hash_pat[ASCII of(main_str[start])], तब
-
हैश_स्ट्र [एएससीआईआई ऑफ (मेन_स्ट्र [स्टार्ट])]:=हैश_स्ट्र [एएससीआईआई ऑफ (मेन_स्ट्र [स्टार्ट])] - 1
-
-
प्रारंभ:=प्रारंभ + 1
-
-
len_window :=j - स्टार्ट + 1
-
अगर min_len> len_window, तब
-
min_len :=len_window
-
start_index :=प्रारंभ
-
-
-
-
अगर start_index -1 के समान है, तो
-
कोई नहीं लौटाएं
-
-
main_str का रिटर्न सबस्ट्रिंग [इंडेक्स start_index से start_index + min_len]
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
N = 256
def get_pattern(main_str, pattern):
str_len = len(main_str)
patt_len = len(pattern)
if str_len < patt_len:
return None
hash_pat = [0] * N
hash_str = [0] * N
for i in range(0, patt_len):
hash_pat[ord(pattern[i])] += 1
start, start_index, min_len = 0, -1, float('inf')
count = 0
for j in range(0, str_len):
hash_str[ord(main_str[j])] += 1
if (hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
count += 1
if count == patt_len:
while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
if (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]):
hash_str[ord(main_str[start])] -= 1
start += 1
len_window = j - start + 1
if min_len > len_window:
min_len = len_window
start_index = start
if start_index == -1:
return None
return main_str[start_index : start_index + min_len]
main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern)) इनपुट
"I am a student", "mdn"
आउटपुट
m a studen
