मान लीजिए कि दो तार A और B हैं। हम कह सकते हैं कि A, B से विभाज्य है, जब A को B को एक या अधिक बार जोड़कर बनाया जाता है। इसलिए यदि A ="abcabc", और B ="abc" है, तो A, B से विभाज्य है। इस खंड में, हम देखेंगे कि स्ट्रिंग का सबसे बड़ा सामान्य भाजक क्या है। तो सबसे बड़ी स्ट्रिंग लौटाएं जो दोनों तारों को विभाजित करती है। तो अगर दो तार "अबाबाब" और "एबीएबी" हैं, तो जीसीडी "एबी" होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- अस्थायी:=ए और बी के बीच छोटी स्ट्रिंग
- m :=तापमान की लंबाई
- x :=1
- res एक सरणी है और रेस में "" डालें
- जबकि A और B में आकार x का सबस्ट्रिंग है, फिर सबस्ट्रिंग को res में जोड़ें, और x को 1 से बढ़ाएँ
- अंत में रेस सरणी में अंतिम तत्व लौटाएं।
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution(object):
def gcdOfStrings(self, str1, str2):
if len(str1)<=len(str2):
temp = str1
else:
temp = str2
m = len(temp)
x = 1
res=[""]
while x<=m:
if m%x==0 and temp[:x] * (len(str1)//x) == str1 and temp[:x] * (len(str2)//x) == str2:
res.append(temp[:x])
x+=1
return res[-1]
ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB","ABAB")) इनपुट
"ABABAB" "ABAB"
आउटपुट
AB