अपने एक साक्षात्कार में मैंने जावा स्ट्रिंग पर एक कार्यक्रम के लिए कहा था, मैं इसका उत्तर देने में असमर्थ हूं। मुझे नहीं पता कि यह एक साधारण या जटिल कार्यक्रम है। मैंने इसके लिए इंटरनेट पर खोजबीन की है, लेकिन इसका सटीक समाधान खोजने में असमर्थ हूं। मेरा प्रश्न इस प्रकार है,

मुझे एक स्ट्रिंग माना जाता है जिसमें रिकर्सिव पैटर्न होता है,

String str1 = "abcabcabc";

उपरोक्त स्ट्रिंग में रिकर्सिव पैटर्न "एबीसी" है जो एक स्ट्रिंग में दोहराया जाता है, क्योंकि इस स्ट्रिंग में केवल "एबीसी" पैटर्न रिकर्सिव होता है।

अगर मैंने इस स्ट्रिंग को किसी फ़ंक्शन/विधि में पैरामीटर के रूप में पास किया है जो फ़ंक्शन/विधि मुझे वापस करनी चाहिए "इस स्ट्रिंग में एक पुनरावर्ती पैटर्न है।" यदि उस स्ट्रिंग में कोई पुनरावर्ती पैटर्न नहीं है तो बस कार्य करें/ विधि को वापस लौटना चाहिए "इस स्ट्रिंग में पुनरावर्ती पैटर्न नहीं है।"

निम्नलिखित संभावनाएं हैं,

String str1 = "abcabcabc"; 
//This string contains recursive pattern 'abc'

String str2 = "abcabcabcabdac"; 
//This string doesn't contains recursive pattern

String str2 = "abcddabcddabcddddabc";
//This string contains recursive pattern 'abc' & 'dd'

क्या कोई मुझे इसके लिए समाधान/एल्गोरिदम सुझा सकता है, मैं इसके साथ संघर्ष कर रहा हूं। विभिन्न संभावनाओं के लिए सबसे अच्छा तरीका क्या है, ताकि मैं कार्यान्वित कर सकूं?

1
Sonali Khaladkar 10 नवम्बर 2017, 12:06

4 जवाब

सबसे बढ़िया उत्तर

LeetCode से

public boolean repeatedSubstringPattern(String str) {
  int l = str.length();
  for(int i=l/2;i>=1;i--) {
      if(l%i==0) {
          int m = l/i;
          String subS = str.substring(0,i);
          StringBuilder sb = new StringBuilder();
          for(int j=0;j<m;j++) {
              sb.append(subS);
          }
          if(sb.toString().equals(str)) return true;
      }
  }
  return false;
}
  1. दोहराए जाने वाले सबस्ट्रिंग की लंबाई इनपुट स्ट्रिंग की लंबाई का विभाजक होना चाहिए
  2. लंबाई/2 से शुरू होकर str.length के सभी संभावित भाजक खोजें
  3. यदि मैं लंबाई का भाजक है, तो 0 से i तक के सबस्ट्रिंग को जितनी बार मैं s.length में समाहित करता हूं, दोहराएं
  4. अगर बार-बार सबस्ट्रिंग इनपुट str रिटर्न ट्रू के बराबर है
3
thebenman 10 नवम्बर 2017, 12:46

समाधान जावास्क्रिप्ट में नहीं है। हालाँकि, समस्या दिलचस्प लग रही थी, इसलिए इसे python में हल करने का प्रयास किया। क्षमा याचना!

python में, मैंने एक तर्क लिखा जो काम करता था [बहुत बेहतर लिखा जा सकता था, सोचा कि तर्क आपकी मदद करेगा]

स्क्रिप्ट है

def check(lst):
    return all(x in lst[-1] for x in lst)

s = raw_input("Enter string:: ")
if check(sorted(s.split(s[0])[1:])):
    print("String, {} is recursive".format(s))
else:
    print("String, {} is NOT recursive".format(s))

स्क्रिप्ट का आउटपुट:

[mac] kgowda@blr-mp6xx:~/Desktop/my_work/play$ python dup.py 
Enter string:: abcabcabcabdac
String, abcabcabcabdac is NOT recursive
[mac] kgowda@blr-mp6xx:~/Desktop/my_work/play$ python dup.py 
Enter string:: abcabcabc
String, abcabcabc is recursive
[mac] kgowda@blr-mp6xx:~/Desktop/my_work/play$ python dup.py 
Enter string:: abcddabcddabcddddabc
String, abcddabcddabcddddabc is recursive
1
Ajay2588 10 नवम्बर 2017, 13:01

इसे Knuth– के एक भाग का उपयोग करके भी हल किया जा सकता है। मॉरिस-प्रैट एल्गोरिथम

शब्द में एक चरित्र का प्रतिनिधित्व करने वाली प्रत्येक प्रविष्टि के साथ 1-डी सरणी बनाने का विचार है। शब्द में प्रत्येक वर्ण i के लिए हम जांचते हैं कि क्या कोई उपसर्ग है जो 0 to i शब्द में एक प्रत्यय भी है। इसका कारण यह है कि यदि हमारे पास सामान्य प्रत्यय और उपसर्ग हैं तो हम उपसर्ग समाप्त होने के बाद भी वर्ण से खोज जारी रख सकते हैं जिसे हम संबंधित वर्ण अनुक्रमणिका के साथ सरणी को अद्यतन करते हैं।

s="abcababcababcab" के लिए, सरणी होगी

Index : 0 1 2 3 4 5 6 7 8 
String: a b c a b c a b c 
KMP   : 0 0 0 1 2 3 4 5 6 

Index = 2 के लिए, हम देखते हैं कि ऐसा कोई प्रत्यय नहीं है जो ab यानी) Index = 2 तक का उपसर्ग भी हो।

Index = 4 के लिए, प्रत्यय ab (इंडेक्स = 3, 4) उपसर्ग ab (इंडेक्स = 0, 1) के समान है, इसलिए हम KMP[4] = 2 को अपडेट करते हैं, जो उस पैटर्न का इंडेक्स है जिससे हमारे पास है खोज फिर से शुरू करने के लिए।

इस प्रकार KMP[i] स्ट्रिंग का सूचकांक रखता है s जहां उपसर्ग 0 to i प्लस 1 श्रेणी में सबसे लंबे समय तक संभव प्रत्यय से मेल खाता है। जिसका अनिवार्य रूप से मतलब है कि लंबाई के साथ उपसर्ग index + 1 - KMP[index] मौजूद है पहले स्ट्रिंग में। इस जानकारी का उपयोग करके हम यह पता लगा सकते हैं कि क्या उस लंबाई के सभी सबस्ट्रिंग समान हैं।

Index = 8 के लिए, हम KMP[index] = 6 जानते हैं, जिसका अर्थ है कि एक उपसर्ग (s[3] to s[5]) लंबाई 9 - 6 = 3 है जो प्रत्यय (s[6] to s[8]) के बराबर है, यदि यह एकमात्र दोहराव वाला पैटर्न है जिसका हमारे पास अनुसरण होगा

इस एल्गोरिथम की स्पष्ट व्याख्या के लिए कृपया यह वीडियो व्याख्यान देखें। इस तालिका को रैखिक समय में बनाया जा सकता है,

vector<int> buildKMPtable(string word)
{
    vector<int> kmp(word.size());
    int j=0;
    for(int i=1; i < word.size(); ++i)
    {
        j = word[j] == word[i] ? j : kmp[j-1];
        if(word[j] == word[i])
        {
             kmp[i] = j + 1;
            ++j;
        }
        else
        {
            kmp[i] = j;
        }
    }
    return kmp;
}

bool repeatedSubstringPattern(string s) {
    auto kmp = buildKMPtable(s);    
    if(kmp[s.size() -1] == 0) // Occurs when the string has no prefix with suffix ending at the last character of the string
    {
        return false;
    }
    int diff = s.size() - kmp[s.size() -1]; //Length of the repetitive pattern
    if(s.size() % diff != 0) //Length of repetitive pattern must be a multiple of the size of the string
    {
        return false;
    }
// Check if that repetitive pattern is the only repetitive pattern. 
    string word = s.substr(0, diff);
    int w_size = word.size();
    for(int i=0; i < w_size; ++i)
    {
        int j = i;
        while(j < s.size())
        {
            if(word[i] == s[j])
            {
                j += w_size;    
            }
            else
            {
                return false;
            }
        }
    }
    return true;
}
1
thebenman 12 नवम्बर 2017, 21:07

यदि आप 'भागों' को पहले से जानते हैं, तो इसका उत्तर पुनरावर्ती रेगुलर एक्सप्रेशन हो सकता है। , लग रहा है।

तो abcabcabc के लिए हमें abc(?R)* जैसे व्यंजक की आवश्यकता है जहां:

  • एबीसी शाब्दिक पात्रों से मेल खाता है
  • (?R) पैटर्न की पुनरावृत्ति करता है
  • ए * शून्य और असीमित संख्या के बीच मिलान करने के लिए

तीसरा थोड़ा पेचीदा है। देखें यह रेगेक्स101 लिंक लेकिन ऐसा लगता है:

((abc)|(dd))(?R)*

जहां हमारे पास या तो 'abc' या 'dd' है और इनमें से कोई भी संख्या है।

अन्यथा, मैं नहीं देखता कि आप केवल एक स्ट्रिंग से कैसे निर्धारित कर सकते हैं कि इसकी कुछ अपरिभाषित रिकर्सिव संरचना है।

0
gilleain 10 नवम्बर 2017, 13:33