Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

feat: implementation of Booth's algorithm for lexicographically minimal rotation of a string.#1759

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
Rudrajiii wants to merge1 commit intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromRudrajiii:master
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
79 changes: 79 additions & 0 deletionsString/BoothsAlgorithm.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
/**
* Booth's Algorithm finds the lexicographically minimal rotation of a string.
* Time Complexity: O(n) - Linear time where n is the length of input string
* Space Complexity: O(n) - Linear space for failure function array
* For More Visit - https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm
* @example
* Input: "baca"
* All possible rotations:
* - "baca"
* - "acab"
* - "caba"
* - "abac"
* Output: "abac" (lexicographically smallest)
*
* How it works:
* 1. Doubles the input string to handle all rotations
* 2. Uses failure function (similar to KMP) to find minimal rotation
* 3. Maintains a pointer to the start of minimal rotation found so far
* @param {string} str - Input string to find minimal rotation
* @returns {string} - Lexicographically minimal rotation of the input string
* @throws {Error} - If input is not a string or is empty
*/
export function findMinimalRotation(str) {
if (typeof str !== 'string') {
throw new Error('Input must be a string')
}

if (str.length === 0) {
throw new Error('Input string cannot be empty')
}

// Double the string for rotation comparison
// This allows us to check all rotations by just sliding a window
const s = str + str
const n = s.length

// Initialize failure function array
const f = new Array(n).fill(-1)
let k = 0 // Starting position of minimal rotation

//Algorithm's implementation
// Iterate through the doubled string
// j is the current position we're examining
for (let j = 1; j < n; j++) {
// i is the length of the matched prefix in the current candidate
// Get the failure function value for the previous position
let i = f[j - k - 1]
// This loop handles the case when we need to update our current minimal rotation
// It compares characters and finds if there's a better (lexicographically smaller) rotation
while (i !== -1 && s[j] !== s[k + i + 1]) {
// If we find a smaller character, we've found a better rotation
// Update k to the new starting position
if (s[j] < s[k + i + 1]) {
// j-i-1 gives us the starting position of the new minimal rotation
k = j - i - 1
}
// Update i using the failure function to try shorter prefixes
i = f[i]
}

// This block updates the failure function and handles new character comparisons
if (i === -1 && s[j] !== s[k + i + 1]) {
// If current character is smaller, update the minimal rotation start
if (s[j] < s[k + i + 1]) {
k = j
}
//If no match found,mark failure function accordingly
f[j - k] = -1
} else {
//If match found, extend the matched length
f[j - k] = i + 1
}
}
// After finding k (the starting position of minimal rotation):
// 1. slice(k): Take substring from position k to end
// 2. slice(0, k): Take substring from start to position k
// 3. Concatenate them to get the minimal rotation
return str.slice(k) + str.slice(0, k)
}
53 changes: 53 additions & 0 deletionsString/test/BoothsAlgorithm.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
import { findMinimalRotation } from '../BoothsAlgorithm'

describe('BoothsAlgorithm', () => {
it('should throw an error if input is not a string', () => {
expect(() => findMinimalRotation(null)).toThrow('Input must be a string')
expect(() => findMinimalRotation(undefined)).toThrow(
'Input must be a string'
)
expect(() => findMinimalRotation(123)).toThrow('Input must be a string')
expect(() => findMinimalRotation([])).toThrow('Input must be a string')
})

it('should throw an error if input string is empty', () => {
expect(() => findMinimalRotation('')).toThrow(
'Input string cannot be empty'
)
})

it('should find minimal rotation for simple strings', () => {
expect(findMinimalRotation('abc')).toBe('abc')
expect(findMinimalRotation('bca')).toBe('abc')
expect(findMinimalRotation('cab')).toBe('abc')
})

it('should handle strings with repeated characters', () => {
expect(findMinimalRotation('aaaa')).toBe('aaaa')
expect(findMinimalRotation('aaab')).toBe('aaab')
expect(findMinimalRotation('baaa')).toBe('aaab')
})

it('should handle strings with special characters', () => {
expect(findMinimalRotation('12#$')).toBe('#$12')
expect(findMinimalRotation('@abc')).toBe('@abc')
expect(findMinimalRotation('xyz!')).toBe('!xyz')
})

it('should handle longer strings', () => {
expect(findMinimalRotation('algorithm')).toBe('algorithm')
expect(findMinimalRotation('rithmalgo')).toBe('algorithm')
expect(findMinimalRotation('gorithmal')).toBe('algorithm')
})

it('should be case sensitive', () => {
expect(findMinimalRotation('AbC')).toBe('AbC')
expect(findMinimalRotation('BcA')).toBe('ABc')
expect(findMinimalRotation('CAb')).toBe('AbC')
})

it('should handle palindromes', () => {
expect(findMinimalRotation('radar')).toBe('adarr')
expect(findMinimalRotation('level')).toBe('ellev')
})
})
[8]ページ先頭
©2009-2025 Movatter.jp