javascript यदि कोई स्ट्रिंग पूरी तरह से एक ही सबस्ट्रिंग से बना है, तो मैं कैसे जांचूं?




string algorithm (10)

मैंने gnasher729 का उत्तर पढ़ा और इसे लागू किया। विचार यह है कि यदि कोई पुनरावृत्ति है, तो पुनरावृत्ति की एक प्रमुख संख्या भी होनी चाहिए।

function* primeFactors (n) {
    for (var k = 2; k*k <= n; k++) {
        if (n % k == 0) {
            yield k
            do {n /= k} while (n % k == 0)
        }
    }
    if (n > 1) yield n
}

function check (str) {
    var n = str.length
    primeloop:
    for (var p of primeFactors(n)) {
        var l = n/p
        var s = str.substring(0, l)
        for (var j=1; j<p; j++) {
            if (s != str.substring(l*j, l*(j+1))) continue primeloop
        }
        return true
    }
    return false
}

थोड़ा अलग एल्गोरिथ्म यह है:

function check (str) {
    var n = str.length
    for (var p of primeFactors(n)) {
        var l = n/p
        if (str.substring(0, n-l) == str.substring(l)) return true
    }
    return false
}

मैंने jsPerf पृष्ठ अपडेट किया है जिसमें इस पृष्ठ पर उपयोग किए गए एल्गोरिदम हैं।

मुझे एक फ़ंक्शन बनाना होगा जो एक स्ट्रिंग लेता है, और यह true या false पर आधारित होना चाहिए कि इनपुट में दोहराए गए वर्ण अनुक्रम शामिल हैं या नहीं। दिए गए स्ट्रिंग की लंबाई हमेशा 1 से अधिक होती है और वर्ण अनुक्रम में कम से कम एक पुनरावृत्ति होनी चाहिए।

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

मैंने नीचे फ़ंक्शन बनाया है:

function check(str){
  if(!(str.length && str.length - 1)) return false;
  let temp = '';
  for(let i = 0;i<=str.length/2;i++){
    temp += str[i]
    //console.log(str.replace(new RegExp(temp,"g"),''))
    if(!str.replace(new RegExp(temp,"g"),'')) return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

इसकी जाँच करना वास्तविक समस्या का हिस्सा है। मैं इस तरह एक गैर कुशल समाधान बर्दाश्त नहीं कर सकता। सबसे पहले, यह स्ट्रिंग के आधे भाग से गुजर रहा है।

दूसरी समस्या यह है कि यह प्रत्येक लूप में replace() का उपयोग कर रहा है जो इसे धीमा कर देता है। क्या प्रदर्शन के संबंध में बेहतर समाधान है?


सरल विचारों में से एक स्ट्रिंग को "" के प्रतिस्थापन के साथ बदलना है और यदि कोई पाठ मौजूद है तो यह गलत है, अन्यथा यह सत्य है।

'ababababa'.replace(/ab/gi,'')
"a" // return false
'abababab'.replace(/ab/gi,'')
 ""// return true


मान लें कि स्ट्रिंग S की लंबाई N है और वह सबरिंग s के डुप्लिकेट से बनी है, तो s की लंबाई N से विभाजित होती है। उदाहरण के लिए, यदि S की लंबाई 15 है, तो प्रतिस्थापन की लंबाई 1, 3, या 5 है।

S की s (p * q) क से बना है। तब S भी (बार-बार q बार) की p प्रतियों से बना होता है। इसलिए हमारे पास दो मामले हैं: यदि N अभाज्य है या 1 है, तो S केवल लंबाई के विकल्प की प्रतियों से बना हो सकता है। 1. यदि N संमिश्र है, तो हमें केवल pr / p विभाजनों के लिए लंबाई N / p के सबस्ट्रिंग की जाँच करने की आवश्यकता है। की लंबाई एस।

इसलिए एन = एस की लंबाई निर्धारित करें, फिर ओ (स्क्वेयर (एन)) में अपने सभी प्रमुख कारकों को ढूंढें। यदि केवल एक कारक N है, तो जांचें कि क्या S एक ही स्ट्रिंग N बार दोहराया गया है, अन्यथा प्रत्येक अभाज्य कारक p के लिए, यदि S में पहले N / p वर्णों के पुनरावर्तन होते हैं।


यदि सूची कम से कम एक बार दोहराई जाती है, तो निम्न गणित कोड लगभग पता लगाता है। यदि स्ट्रिंग को कम से कम एक बार दोहराया जाता है, तो यह सच हो जाता है, लेकिन यदि स्ट्रिंग बार-बार तार का एक रैखिक संयोजन है, तो यह भी सही हो सकता है।

IsRepeatedQ[list_] := Module[{n = [email protected]},
   [email protected]@Sum[list[[i]] Exp[2 Pi I i/n], {i, n}] == 0
];

यह कोड "पूर्ण-लंबाई" योगदान के लिए दिखता है, जिसे दोहराए जाने वाले स्ट्रिंग में शून्य होना चाहिए, लेकिन स्ट्रिंग accbbd को भी दोहराया जाना माना जाता है, क्योंकि यह दो दोहराया स्ट्रिंग ababab और 012012

विचार फास्ट फूरियर ट्रांसफॉर्म का उपयोग करना है, और आवृत्ति स्पेक्ट्रा की तलाश करना है। अन्य आवृत्तियों को देखकर, इस अजीब परिदृश्य का भी पता लगाने में सक्षम होना चाहिए।


मुझे लगता है कि एक पुनरावर्ती कार्य बहुत तेज हो सकता है। पहला अवलोकन यह है कि कुल स्ट्रिंग के रूप में अधिकतम दोहराया पैटर्न की लंबाई आधी है। और हम सिर्फ सभी संभव दोहराया पैटर्न लंबाई का परीक्षण कर सकते हैं: 1, 2, 3, ..., str.length / 2

यदि इस पैटर्न को स्ट्रेट में दोहराया जाता है, तो पुनरावर्ती फ़ंक्शन रीपिटिंग (पी, स्ट्र) का परीक्षण करता है।

यदि पैटर्न से अधिक लंबा है, तो पुनरावृत्ति के लिए पुनरावृत्ति के साथ-साथ str के शेष भाग के पहले भाग (p के समान लंबाई) की आवश्यकता होती है। तो str प्रभावी रूप से लंबाई p.length के टुकड़ों में टूट जाता है।

यदि परीक्षण किया गया पैटर्न और str समान आकार के हैं, तो पुनरावृत्ति यहाँ समाप्त होती है, सफलतापूर्वक।

यदि लंबाई अलग है ("aba" और पैटर्न "ab" के लिए होता है) या यदि टुकड़े अलग-अलग हैं, तो झूठे को वापस लाया जाता है, पुनरावृत्ति का प्रचार करता है।

function check(str)
{
  if( str.length==1 ) return true; // trivial case
  for( var i=1;i<=str.length/2;i++ ) { // biggest possible repeated pattern has length/2 characters

    if( str.length%i!=0 ) continue; // pattern of size i doesn't fit
    
    var p = str.substring(0, i);
    if( isRepeating(p,str) ) return true;
  }
  return false;
}


function isRepeating(p, str)
{
  if( str.length>p.length ) { // maybe more than 2 occurences

    var left = str.substring(0,p.length);
    var right = str.substring(p.length, str.length);
    return left===p && isRepeating(p,right);
  }
  return str===p; 
}

console.log(check('aa')) //true
console.log(check('aaa')) //true 
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

प्रदर्शन: https://jsperf.com/reegx-and-loop/13


आप इसे कैप्चरिंग ग्रुप और backreference द्वारा कर सकते हैं। बस जाँच करें कि यह पहले कैप्चर किए गए मान की पुनरावृत्ति है।

function check(str) {
  return /^(.+)\1+$/.test(str)
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

उपरोक्त RegExp में:

  1. स्थिति की भविष्यवाणी करने के लिए शुरुआत और अंत एंकर के लिए ^ और $ खड़ा है।
  2. (.+) किसी भी पैटर्न को पकड़ता है और मूल्य ( \n को छोड़कर) को कैप्चर करता है।
  3. पहले कब्जा किए गए मूल्य का बैकरेस्ट \1 है और कब्जा किए गए मूल्य की पुनरावृत्ति के लिए जाँच करेगा।

रेगेक्स स्पष्टीकरण यहाँ

RegExp डीबगिंग उपयोग के लिए: https://regex101.com/r/pqlAuP/1/debugger

प्रदर्शन: https://jsperf.com/reegx-and-loop/13


इसे पायथन में लिखा। मुझे पता है कि यह मंच नहीं है, लेकिन इसमें 30 मिनट का समय लगा। पीएस => पायथन

def checkString(string):
    gap = 1 
    index= 0
    while index < len(string)/2:
        value  = [string[i:i+gap] for i in range(0,len(string),gap) ]

        x = [string[:gap]==eachVal for eachVal in value]

        if all(x):
            print("THEY ARE  EQUAL")
            break 

        gap = gap+1
        index= index+1 

checkString("aaeaaeaaeaae")

यहां मूल विचार किसी भी संभावित विकल्प की जांच करना है, जिसकी लंबाई 1 से शुरू होती है और मूल स्ट्रिंग की लंबाई के आधे भाग पर रुकती है। हम केवल मूल स्ट्रिंग की लंबाई को विभाजित करने वाली लंबाई (यानी str.length% substring.length = 0) को विभाजित करते हुए देखते हैं।

यह कार्यान्वयन दूसरे वर्ण पर जाने से पहले प्रत्येक संभव प्रतिस्थापन पदार्थ के पहले चरित्र को देखता है, जो समय बचाने के लिए हो सकता है अगर सबस्ट्रिंग लंबे होने की उम्मीद है। यदि पूरे सबस्ट्रिंग की जांच करने के बाद कोई बेमेल नहीं पाया जाता है, तो हम सच लौटते हैं।

जब हम जांच करने के लिए संभावित सबस्ट्रिंग से बाहर निकलते हैं तो हम झूठे हो जाते हैं।

function check(str) {
  const len = str.length;
  for (let subl = 1; subl <= len/2; ++subl) {
    if ((len % subl != 0) || str[0] != str[subl])
      continue;
    
    let i = 1;
    for (; i < subl; ++i)
    {
      let j = 0;
      for (; j < len; j += subl)
        if (str[i] != str[j + i])
          break;
      if (j != len)
        break;
    }
    
    if (i == subl)
      return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false


मैं जावास्क्रिप्ट से परिचित नहीं हूं, इसलिए मुझे नहीं पता कि यह कितनी तेजी से होने वाला है, लेकिन यहां केवल बिल्डिंस का उपयोग करके एक रैखिक समय समाधान (उचित बिलिन कार्यान्वयन को संभालने) है। मैं pseudocode में एल्गोरिथ्म का वर्णन करता हूँ।

function check(str) {
    t = str + str;
    find all overlapping occurrences of str in t;
    for each occurrence at position i
        if (i > 0 && i < str.length && str.length % i == 0)
            return true;  // str is a repetition of its first i characters
    return false;
}

विचार एमबीओ के उत्तर के समान है। प्रत्येक के लिए जो लंबाई को विभाजित करता है, str अपने पहले i वर्णों की पुनरावृत्ति है यदि और केवल अगर यह i वर्णों के लिए स्थानांतरण के बाद भी ऐसा ही रहता है।

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


शायद सबसे तेज़ एल्गोरिथम दृष्टिकोण रैखिक समय में एक Z-function का निर्माण कर रहा है:

इस स्ट्रिंग के लिए जेड-फ़ंक्शन लंबाई n की एक सरणी है जहां i-th तत्व उस स्थिति से शुरू होने वाले सबसे बड़ी संख्या के बराबर है जो कि मैं पहले अक्षर के साथ मेल खाता हूं।

दूसरे शब्दों में, z [i] s और i पर शुरू होने वाले s के प्रत्यय के बीच सबसे लंबे सामान्य उपसर्ग की लंबाई है।

संदर्भ के लिए C ++ कार्यान्वयन:

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

जावास्क्रिप्ट कार्यान्वयन
जोड़ा अनुकूलन - z- सरणी और जल्दी बाहर निकलने का एक आधा निर्माण

function z_function(s) {
  var n = s.length;
  var z = Array(n).fill(0);
  var i, l, r;
  //for our task we need only a half of z-array
  for (i = 1, l = 0, r = 0; i <= n/2; ++i) {
    if (i <= r)
      z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
      ++z[i];

      //we can check condition and return here
     if (z[i] + i === n && n % i === 0) return true;
    
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return false; 
  //return z.some((zi, i) => (i + zi) === n && n % i === 0);
}
console.log(z_function("abacabacabac"));
console.log(z_function("abcab"));

फिर आपको उन अनुक्रमितों की जांच करने की आवश्यकता है जो i विभाजित करते हैं n। अगर आपको ऐसा लगता है कि i+z[i]=n तो स्ट्रिंग s को लंबाई i संपीड़ित किया जा सकता है और आप true वापसी कर सकते हैं।

उदाहरण के लिए, के लिए

string s= 'abacabacabac'  with length n=12`

z- सरणी है

(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)

और हम इसके लिए पा सकते हैं

i=4
i+z[i] = 4 + 8 = 12 = n
and
n % i = 12 % 4 = 0`

इसलिए s को 4 बार तीन बार लंबाई के विकल्प के रूप में दर्शाया जा सकता है।





algorithm