JavaScript 프로그램은 문자열이 서로에 대해 회전하는지 확인합니다.

줄이 서로 회전한다는 것은 두 개의 줄을 오른쪽이나 왼쪽으로 회전하여 다른 줄을 얻을 수 있다는 의미입니다. 문자열의 오른쪽으로 회전된 문자에서 다음 인덱스로 이동하고, 문자열이 원 안에 있다고 가정하고 0번째 인덱스의 경우 마지막 인덱스의 문자를 가져옵니다. 왼쪽 회전은 오른쪽 회전과 유사하지만 반대 방향입니다. 두 개의 문자열이 주어지고 한 문자열의 문자를 회전하여 다른 문자열을 얻을 수 있는지 결정해야 합니다.

들어가세요

으아아아

출력

으아아아

설명: 첫 번째 문자열을 왼쪽으로 두 번 회전하여 두 번째 문자열을 얻을 수 있습니다. 첫 번째 루프 이후의 String1은 "bcdefa"가 되고 다음 루프에서는 두 번째 문자열과 동일하게 됩니다.

들어가세요

으아아아

출력

으아아아

설명 - 원래 문자열을 가져오지 않고 문자열이나 배열을 회전할 수 있는 최대 회전 수는 주어진 문자열이나 배열의 길이와 같습니다.

여기서 6회전 후에는 문자열 1에서 문자열 2를 얻을 수 없으며, 이는 최대 회전 수 이후 두 문자열을 동일하게 만드는 것이 불가능하다는 것을 증명합니다.

순진한 방법

이 방법에서는 주어진 문자열을 길이만큼 회전하고 다른 주어진 문자열과 일치시킵니다.

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N*N)입니다. 여기서 N은 주어진 문자열의 크기입니다.

위 코드의 공간 복잡도는 공간을 사용하지 않기 때문에 O(1)입니다.

KMP 알고리즘

이 프로그램에서는 KMP 알고리즘을 사용하여 회전을 찾습니다. 코드로 이동해 보겠습니다.

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 프로그램의 경우 시간 복잡도와 공간 복잡도는 모두 O(N)입니다. lps 배열에 값을 저장하기 위해 추가 공간을 사용합니다.

결론

이 튜토리얼에서는 문자열의 문자를 왼쪽이나 오른쪽으로 회전하여 주어진 문자열을 다른 주어진 문자열에서 얻을 수 있는지 확인하는 JavaScript 프로그램을 구현했습니다. 우리는 O(N*N) 시간 복잡도와 O(1) 공간 복잡도를 취하는 순진한 접근 방식을 사용했습니다. 또한 O(N) 시간 및 공간 복잡도를 갖는 KMP 알고리즘을 구현했습니다.

위 내용은 JavaScript 프로그램은 문자열이 서로에 대해 회전하는지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!