JavaScript로 문자열이 반복된 부분 문자열의 조합인지 확인하는 방법

문제 상황

문자열을 인수로 하나 받아서, 해당 문자열이 자신의 일부분(부분 문자열)을 여러 번 반복하여 이어 붙인 형태인지 판별하는 JavaScript 함수를 작성해야 합니다.

예를 들어 함수의 입력이 다음과 같다면 −

const str = 'thisthisthisthis';

출력 결과는 다음과 같아야 합니다 −

const output = true;

출력 설명

'thisthisthisthis'라는 문자열은 'this'라는 부분 문자열을 네 번 반복해서 이어 붙인 것이기 때문에 결과는 true가 됩니다. 반면 'abcdab'처럼 동일한 패턴으로 나누어 떨어지지 않는 문자열이라면 false를 반환해야 합니다.

해결 코드

이 문제를 해결하는 코드는 다음과 같습니다 −

const str = 'thisthisthisthis';
const repeatedSubstring = (str = '') => {
    const {length} = str;
    const checkSubString = ss => {
        const m = ss.length;
        for (let i = 0; i < length; i += m)
            for (let j = 0; j < m; j++)
                if (str[i+j] !== ss[j])
                    return false;
        return true;
    };
    let factor = 2, len;
    while (length/factor >= 1){
        while (length % factor) factor++;
        len = length/factor;
        if (checkSubString(str.substring(0,len))){
            return true;
        };
        factor++;
    };
    return false;
};
console.log(repeatedSubstring(str));

코드 설명

코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1단계: 먼저 주어진 부분 문자열 패턴이 전체 문자열과 일치하는지 검사하는 checkSubString 헬퍼 함수를 정의합니다. 이 함수는 후보 패턴을 받아서 문자열 전체를 순회하며 패턴이 반복적으로 일치하는지 확인합니다.

2단계: 문자열 길이를 나누어 떨어지게 하는 모든 약수(factor)를 순회하면서, 각 약수에 해당하는 길이만큼의 접두사를 부분 문자열 후보로 추출합니다.

3단계: 각 후보 패턴에 대해 반복 검사를 수행하고, 하나라도 성공하면 true를 반환합니다. 모든 경우를 확인했는데도 적절한 반복 패턴이 없다면 false를 반환합니다.

이 접근 방식의 시간 복잡도는 대략 O(n × d)입니다. 여기서 n은 문자열의 길이, d는 n의 약수 개수입니다. 약수의 개수는 일반적으로 매우 작기 때문에 실제로는 효율적으로 동작합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

true