javascript - 함수 - 문자열이 완전히 동일한 하위 문자열로 구성되었는지 확인하려면 어떻게합니까?




자바스크립트 startswith (8)

JavaScript에 익숙하지 않아서 이것이 얼마나 빨라지는지 알지 못하지만 여기에는 내장 함수 만 사용하는 선형 시간 솔루션 (합리적인 내장 구현을 가정)이 있습니다. 의사 코드에서 알고리즘을 설명하겠습니다.

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

아이디어는 MBo의 대답과 유사합니다. 길이를 나눈 각각의 i 대해, stri 문자를 이동 한 후에 동일하게 남아있는 경우에만 첫 번째 i 문자의 반복입니다.

그러한 내장 기능을 사용할 수 없거나 비효율적 일 수 있습니다. 이 경우 항상 KMP 알고리즘을 수동으로 구현할 수 있습니다.이 알고리즘은 MBo의 알고리즘과 거의 동일한 양의 코드를 사용합니다.

나는 문자열을 취하는 함수를 만들어야하고 입력이 반복 된 문자 시퀀스로 구성되어 있는지에 따라 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() 를 사용하여 속도를 느리게하는 것입니다. 성능면에서 더 나은 솔루션이 있습니까?


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


나의 접근 방식은 부분 초점의 주요 길이를 잠재적 인 길이로 사용한다는 점에서 gnasher729와 유사하지만 수학과 프로세스가 덜 필요합니다.

L : 원래 문자열의 길이

S : 유효한 하위 문자열의 잠재적 길이

L / 2가 1 인 경우 L / S를 정수로 변환합니다. 원래 문자열이 주 문자열 S와 비교하여 원래 문자열이 L / S 횟수만큼 반복되었는지 확인하십시오.

L / 2에서 역순으로 반복하는 이유는 가능한 최대 부분 문자열을 얻는 것입니다. 가능한 한 가장 작은 하위 문자열 루프를 1에서 L / 2로 지정하려는 경우 예 : "abababab"에는 "ab"와 "abab"이 가능한 하위 문자열로 있습니다. true / false 결과에만 신경 쓰면 더 빨라지는 두 문자열 중 어느 것이 적용될 문자열 / 하위 문자열 유형에 따라 달라집니다.


다음 Mathematica 코드는 목록이 적어도 한 번 반복되면 거의 감지합니다. 문자열이 적어도 한 번 반복되면 true를 반환하지만 문자열이 반복되는 문자열의 선형 조합 인 경우 true를 반환 할 수도 있습니다.

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

이 코드는 "full-length"기여도를 찾습니다.이 기여도는 반복되는 문자열에서 0이어야하지만 ababab012012 라는 두 개의 반복 된 문자열의 합계이므로 accbbd 문자열도 반복 된 것으로 간주됩니다.

아이디어는 고속 푸리에 변환을 사용하고 주파수 스펙트럼을 찾습니다. 다른 주파수를 보면이 이상한 시나리오도 감지 할 수 있어야합니다.


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

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

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

그런 다음 n을 나눌 인덱스 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 는 3 번 반복 된 길이 4의 부분 문자열로 표현 될 수 있습니다.


여기서 기본 아이디어는 길이 1에서 시작하여 원래 문자열의 길이의 절반으로 멈추는 잠재적 하위 문자열을 검사하는 것입니다. 원래 문자열 길이를 균등하게 나눈 부분 문자열 만 봅니다 (예 : str.length % substring.length == 0).

이 구현은 두 번째 문자로 이동하기 전에 가능한 각 하위 문자열 반복의 첫 번째 문자를 확인하므로 하위 문자열이 길어질 것으로 예상되는 경우 시간을 절약 할 수 있습니다. 부분 문자열 전체를 검사 한 후에 불일치가 발견되지 않으면 true를 반환합니다.

확인할 잠재적 하위 문자열이 부족할 경우 false를 반환합니다.

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


이런 문자열에 관해서는 멋진 정리가 있습니다.

문자열은 그 자체의 중요한 회전이 아닌 경우에만 여러 번 반복되는 동일한 패턴으로 구성됩니다.

여기서 회전은 문자열 앞에서 몇 개의 문자를 삭제하고 뒤쪽으로 옮기는 것을 의미합니다. 예를 들어 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가 첫 번째 또는 중간 문자에서 일치하지 않고 xx의 하위 문자열인지 확인해야합니다. 다음은 그 한 가지 예입니다.

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

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

희망이 도움이!


재귀 함수가 매우 빠르다고 생각합니다. 첫 번째 관찰은 최대 반복 패턴 길이가 전체 문자열의 절반 인 것입니다. 가능한 모든 반복 패턴 길이를 테스트 할 수 있습니다 : 1, 2, 3, ..., str.length / 2

재귀 함수 isRepeating (p, str)은이 패턴이 str에서 반복되는지 테스트합니다.

str이 패턴보다 길면 재귀는 첫 번째 부분 (p와 같은 길이)이 반복이고 str의 나머지 부분이 필요합니다. 따라서 str은 길이가 p.length 인 조각으로 효과적으로 나뉩니다.

테스트 된 패턴과 str의 크기가 같으면 여기에서 재귀가 성공적으로 끝납니다.

길이가 다른 경우 ( "aba"및 패턴 "ab"에 대해 발생) 또는 조각이 다른 경우 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

실적 : https://jsperf.com/reegx-and-loop/13





algorithm