문자열이 완전히 동일한 하위 문자열로 구성되어 있는지 어떻게 확인합니까?

문자열이 완전히 동일한 하위 문자열로 구성되어 있는지 어떻게 확인합니까?

---

I 문자열을 취하는 함수를 작성해야하고, 그 반환해야 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()각 루프에서 사용하므로 속도가 느려진다는 것입니다. 성능과 관련하여 더 나은 솔루션이 있습니까?

---

이와 같은 문자열에 대한 멋진 작은 정리가 있습니다.

문자열은 문자열 자체가 사소한 회전 인 경우에만 여러 번 반복되는 동일한 패턴으로 구성됩니다.

여기서 회전이란 문자열 앞쪽에서 몇 개의 문자를 삭제하고 뒤쪽으로 이동하는 것을 의미합니다. 예를 들어 문자열 hello을 회전하여 다음 문자열 중 하나를 형성 할 수 있습니다.

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

이것이 왜 작동하는지 확인하려면 먼저 문자열이 문자열 w의 k 반복 사본으로 구성되어 있다고 가정하십시오. 그런 다음 반복 된 패턴의 첫 번째 사본 (w)을 끈의 앞면에서 삭제하고 뒷면에 ​​타킹하면 같은 문자열이 나타납니다. 반대 방향은 약간 까다로울 수 있지만 문자열을 회전하고 시작한 항목을 다시 가져 오면 동일한 회전의 패턴을 가진 여러 복사본으로 문자열을 바둑판 식으로 배열하기 위해 회전을 반복적으로 적용 할 수 있다는 아이디어입니다. 회전을 위해 끝으로 이동 해야하는 문자열).

이제 질문은 이것이 사실인지 확인하는 방법입니다. 이를 위해 사용할 수있는 또 다른 아름다운 정리가 있습니다.

x와 y가 같은 길이의 문자열이면 x가 yy의 하위 문자열 인 경우에만 x는 y의 회전입니다.

예를 들어, 다음과 같이 lohel회전 함을 알 수 있습니다 hello.

hellohello
   ^^^^^

우리의 경우 모든 문자열 x는 항상 xx의 하위 문자열이됩니다 (x의 각 복사본마다 한 번씩 두 번 나타남). 따라서 기본적으로 문자열 x가 첫 번째 또는 중간 문자와 일치하지 않고 문자열 x가 xx의 하위 문자열인지 확인하면됩니다. 여기에 하나의 라이너가 있습니다.

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

indexOf빠른 문자열 일치 알고리즘을 사용하여 구현 한다고 가정하면 시간 O (n)에서 실행되며 여기서 n은 입력 문자열의 길이입니다.

도움이 되었기를 바랍니다!

---

캡처 그룹 과 역 참조를 통해이를 수행 할 수 있습니다 . 처음 캡처 된 값이 반복되는지 확인하십시오.

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첫 번째 캡처 된 값의 역 참조이며 캡처 된 값의 \1+반복을 확인합니다.

여기에 정규식 설명

RegExp 디버깅의 경우 https://regex101.com/r/pqlAuP/1/debugger

성능 : https://jsperf.com/reegx-and-loop/13

---

아마도 가장 빠른 알고리즘 접근법은 선형 시간으로 Z 함수 를 작성하는 것입니다.

이 문자열의 Z- 함수는 길이 n의 배열이며, i 번째 요소는 s의 첫 문자와 일치하는 위치 i에서 시작하여 최대 문자 수와 같습니다.

즉, z [i]는 s와 i에서 시작하는 접미사 사이의 가장 긴 공통 접두사 길이입니다.

참조를위한 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;
}

JavaScript 구현
최적화 추가-z-array의 절반 및 조기 종료 빌드

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"));

그런 다음 in을 나누는 인덱스를 확인해야합니다 . 당신이 그런 발견하면 i것을 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의 3 회 반복 하위 문자열로 표현 될 수 있습니다.

---

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 페이지 를 업데이트했습니다 .

---

Assume the string S has length N and is made of duplicates of the substring s, then the length of s divides N. For example, if S has length 15, then the substring has length 1, 3, or 5.

Let S be made of (p*q) copies of s. Then S is also made of p copies of (s, repeated q times). We have therefore two cases: If N is prime or 1, then S can only be made of copies of the substring of length 1. If N is composite, then we only need to check substrings s of length N / p for primes p dividing the length of S.

So determine N = the length of S, then find all its prime factors in time O (sqrt (N)). If there is only one factor N, check if S is the same string repeated N times, otherwise for each prime factor p, check if S consists of p repeations of the first N / p characters.

---

I think a recursive function might be very fast as well. The first observation is that the maximum repeated pattern length is half as long as the total string. And we could just test all possible repeated pattern lengths: 1, 2, 3, ..., str.length/2

The recursive function isRepeating(p,str) tests if this pattern is repeated in str.

If str is longer than the pattern, the recursion requires the first part (same length as p) to be a repetition as well as the remainder of str. So str is effectively broken up into pieces of length p.length.

If the tested pattern and str are of equal size, recursion ends here, successfully.

If the length is different (happens for "aba" and pattern "ab") or if the pieces are different, then false is returned, propagating up the recursion.

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

Performance: https://jsperf.com/reegx-and-loop/13

---

Wrote this in Python. I know it is not the platform, but it did take 30 mins of time. P.S.=> PYTHON

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")

---

My approach is similar to gnasher729, in that it uses the potential length of the substring as the main focus, but it is less math-y and process intensive:

L: Length of original string

S: Potential lengths of valid sub-strings

Loop S from (integer part of) L/2 to 1. If L/S is an integer check your original string against the fist S characters of the original string repeated L/S times.

The reason for looping from L/2 backwards and not from 1 onwards is to get the largest possible substring. If you want the smallest possible substring loop from 1 to L/2. Example: "abababab" has both "ab" and "abab" as possible substrings. Which of the two would be faster if you only care about a true/false result depends on the type of strings/substrings this will be applied to.

---

The following Mathematica code almost detects if the list is repeated at least once. If the string is repeated at least once, it returns true, but it might also return true if the string is a linear combination of repeated strings.

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

This code looks for the "full-length" contribution, which must be zero in a repeating string, but the string accbbd is also considered repeated, as it is a sum of the two repeated strings ababab and 012012.

The idea is to use Fast Fourier Transform, and look for the frequency spectra. By looking at other frequencies, one should be able to detect this strange scenario as well.

---

The basic idea here is to examine any potential substring, beginning at length 1 and stopping at half of the original string's length. We only look at substring lengths that divide the original string length evenly (i.e. str.length % substring.length == 0).

This implementation looks at the first character of each possible substring iteration before moving to the second character, which might save time if the substrings are expected to be long. If no mismatch is found after examining the entire substring, then we return true.

We return false when we run out of potential substrings to check.

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

---

I'm not familiar with JavaScript, so I don't know how fast this is going to be, but here is a linear time solution (assuming reasonable builtin implementation) using only builtins. I'll describe the algorithm in 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;
}

The idea is similar to MBo's answer. For each i that divides the length, str is a repetition of its first i characters if and only if it remains the same after shifting for i characters.

It comes to my mind that such a builtin may be unavailable or inefficient. In this case, it is always possible to implement the KMP algorithm manually, which takes about the same amount of code as the algorithm in MBo's answer.

---

One of the simple ideas is to replace the string with the substring of "" and if any text exist then it is false, else it is true.

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

참고URL : https://stackoverflow.com/questions/55823298/how-do-i-check-if-a-string-is-entirely-made-of-the-same-substring