[javascript] 문자열이 완전히 동일한 하위 문자열로 만들어 졌는지 어떻게 확인합니까?

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

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

여기서 회전이란 문자열 앞쪽에서 몇 개의 문자를 삭제하고 뒤쪽으로 이동하는 것을 의미합니다. 예를 들어 문자열 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

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;
}

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

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

(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`

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
}

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

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