Understanding whether one string is a rotation of another is a common technical problem that often arises in coding interviews and real-world applications such as data alignment and cryptography. A typical solution involves concatenating strings, but here we explore a method that doesn't require this approach.

Problem Statement

Given two strings, `s1` and `s2`, determine if one string is a rotation of the other. A string rotation involves moving characters from the beginning of the string to the end without rearranging their order.

Constraints

• Both strings must be of equal length.
• We are forbidden from using concatenation to solve the problem.

Approach Without Concatenation

To solve this problem without concatenating strings, we can use an alternative approach that leverages pattern matching algorithms such as the Knuth-Morris-Pratt (KMP) algorithm or use an auxiliary vector to represent rotations.

Solution Explanation

Key Idea

A rotation implies that a substring of the original string can start somewhere in the array of characters and continues to wrap around to the beginning. Thus, we can visualize the problem as a circular string matching problem.

Steps

1. Length Check:
   • First, check if both strings have the same length. If not, they cannot be rotations.
2. Double-Length Array:
   • Construct a double-length array of both strings. This is an imaginary operation to conceptualize how rotation works without actually altering strings.
3. Pattern Matching:
   • Use the KMP algorithm or other efficient pattern-matching algorithms that can find a substring within this hypothetical double array.

KMP Algorithm Application

The KMP algorithm can be adapted to perform this efficiently:

1. Prefix Table Construction:
   • Construct the prefix table for the second string, `s2`.
2. Pattern Match Simulation:
   • Iterate through `s1` as if it were continuous (think of it as a circular buffer) using the prefix table to skip unnecessary comparisons.

Example

Consider `s1 = "waterbottle"` and `s2 = "erbottlewat"`:

• Use a prefix table for `s2` to optimize the search.
• Attempt to match `s2` within `s1` treated as a circular array.

Code Implementation