SPyofgame's blog

Lexicographically Minimal String Rotation
By SPyofgame, history, 3 years ago, In English

Table of content

Teleporter Description
I. The Problem Describe about the problem
II. Bruteforce Approach Simple way to do the problem
III. Hashing Approach Reduce circular substring comparing complexity
IV. Sqrt Decomposition Divide into parts, solve each part then solve the whole part
V. KMP Approach Magical Linear Booth-KMP Algorithm
VI. Lyndon Factorization Approach Incredible Linear Duval-Lyndon Algorithm
VII. Suffix Array Approach Hard for constructing but simple to find result
VIII. Suffix Automation Approach Complex Linear Construction but simple to find result
IX. Elimination Tournament Algorithm From initial candidates, eliminate worst candidates until find one final champion
................................................................... ..........................................................................................................................

I. The Problem

A) The problem:

1) Statement:

Sometimes being as a coder, you will find some real life problems about strings. Some strings are just simple an array of characters with 2 ended. Sometimes you will face with circular strings, the one which circular around. Let take you to the biological laboratory, dont worry, I just teleport you without requiring any money. In the lab, you will find many interesting bacteria. How could you detect which one is belonged to the same group or not ? Let simplify the problem that two bacteria are in the same group if their circular encoded-DNA strings are the same. So how can you compare two randomly encoded-DNA ? One of the effectively way to do that is convert all strings into Minimal Lexicographical Acyclic Strings (a.k.a Lexicographically Minimal String Rotation) and then hash them for faster comparison.

This bring down to a much simpler problem. Let define a right-rotation of a string is that putting the leftmost character to the rightmost position. Given circular DNA string $$$S$$$ of size $$$n$$$. Find the minimum right-rotation to make it Minimal Lexicographical for all such rotations.

2) Question:

  • Given a string of latin words $$$S$$$ of size $$$N$$$

  • A right-rotation of $$$S$$$ is that $$$S_2 + S_3 + ... + S_{|S|} + S_1$$$ where ('+' notation mean concatenation)

  • Find the least right-rotation to make $$$S$$$ become the Lexicographically Minimal

3) Constraint:

  • $$$S$$$ is a string of lower latin (you can expand the problem to $$$A$$$ is an array of integers)

  • $$$|S| \leq 10^5$$$ (you can also expand the limit to $$$10^6$$$ or even higher)

4) Example:
Example 1
Example 2
Example 3
Example 4
Example 5
Example 6
Example 7
Example 8
Example 9
Example 10
Example 11
Example 12
Example 13
All Examples As Once

B) Real Life Applications

1) Finger print identification:
  • We can encode the finger print into many detailed circular strings. How to search such finger print again from those in very huge data base ? Circular comparision using lyndon factorization is requried.
2) Biological genetics:
  • In some cases, we need to know whether these two group's genetics are belonged to the same bacteria, virus.
3) Games:
  • Well, ofcourse we can apply the algorithm in some language/words-related games

C) Practice Links

1) CSES — Minimal Rotation
  • Require: Output least rotation string with $$$|S| \leq 10^6$$$
2) SPOJ — Minimum Rotations
  • Require: Output least rotation number with $$$|S| \leq 10^5$$$
3) UVA — Glass Beads
  • Require: Queries output least rotation number with $$$|S| \leq 10^4$$$

II. Bruteforce Apprach

A) Sorting and Searching:

1) Idea:

  • We will take all possible circular substring in $$$S$$$

  • For every possible rotation of the string, we add it with its number of rotations needed

  • Then we sort all the array by their string (if they are equal, we take one with its smaller index).

  • The answer will be the smallest string (minimal lexicographical) with its lowest index.

2) Complexity:

  • Compare two random strings $$$S$$$ and $$$T$$$ cost $$$O(min(|S|, |T|)) = O(n)$$$ (since $$$|S| = |T| = n$$$)

  • The complexity of sorting all array is $$$O(n log n)$$$

  • Hence the total complexity is $$$O(n^2 log n)$$$

3) Implementations:
Vector Sorting Bruteforce Solution - O(n^2 log(n)) time - O(n^2) auxiliary space
Map Sorting Bruteforce Solution - O(n^2 log(n)) time - O(n^2) auxiliary space

B) Loop over all rotations:

1) Idea:
  • Why should we store then sort anyway, we just need to loop over all rotations and comparing to select the smaller
2) Implementations:

  • For convention, you can just duplicate the string $$$T = S + S$$$

  • Then $$$S$$$ at the $$$ith$$$ rotations ($$$0 \leq i < n$$$) is the string $$$T[i \dots i + n]$$$

Bruteforce Solution - O(n^2) time - O(n) auxiliary space
3) Optimization:

  • By quickly break when the two strings arent equal, this can optimize the function a little bit

  • Instead of making duplicated string, you can also define $$$s[x] = s[x\ mod\ |s|]$$$ since $$$s$$$ itself is a circular string

  • Instead of taking modulo, since $$$0 \leq x < 2 * n$$$, we just need reduce $$$x$$$ by $$$n$$$ whenever it passed $$$n$$$

Optimized Bruteforce Solution - O(n^2) time - O(1) auxiliary space

C) Substring Based Elimination

1) Idea:
  • From inital set of candidates, keep comparing substrings and eliminate the bigger one until we get the final champion
2) Algorithm:
  • First, let $$$mn$$$ / $$$mx$$$ is the minimal / maximal character of $$$s$$$

Define: $$$mn = \underset{c \in S}{min}(c)$$$ and $$$mx = \underset{c \in S}{max}(c)$$$

  • Pre-elimination Round: We take the position $$$p$$$ that $$$s[p] = mn$$$. Since all other positions wont provide Minimal Lexicographical Circular String

Define: $$$candidate = $$$ { $$$p\ \ |\ \ p \in $$$ { $$$0, 1, \dots, |s| - 1$$$ } $$$ \cap s[p] = mn$$$ }

  • Then we take maximumly $$$n - 1$$$ Rounds from $$$d = 1$$$ to $$$d = n - 1$$$. For all current candidate, add the next character to it. Find the minimal substring, and eliminater unsatisfied others.
2) Optimization

Optimization: At the $$$p$$$ round we will find $$$c = $$$ minimal character among all candidate's $$$pth$$$-next character, then traverse again and eliminate the one whose $$$pth$$$-nxt character is greater than $$$c$$$

Define: $$$s[x] = s[x\ mod\ |s|]$$$ and $$$c = \underset{p \in\ candidate}{min}(s[p + d])$$$ and $$$next\ candidate = $$$ { $$$p\ \ |\ \ p \in candidate \cap s[p + d] = c$$$ }

3) Example:
  • $$$S = $$$"$$$abaabaaabaababaaabaaababaab$$$"
Pre-elimination - 26 candidates
Round I - 18 candidates
Round II - 9 candidates
Round III - 3 candidates
Round IV - 3 candidates
Round V - 3 candidates
Round VI - 2 candidates
Champion
4) Notice
  • After all eliminations, if there are more than one candidate, select the one with lowest index
5) Complexity

  • If the string is $$$k$$$-repeated strings (each substring size $$$d$$$) or similar then there will be atleast $$$k$$$ candidate after $$$d$$$ eliminations. About $$$O(k \times d)$$$ in the best cases

  • Best case to say, like a string where all characters are unique, then it will be Linear $$$O(n)$$$

  • Worst case to say, like a string where all characters are the same, then it will be $$$O(n \times n) = O(n^2)$$$

6) Implementations
  • For convention, let not use obviously-not-optimized code
Detail Substring Based Elimination - O(n^2) time - O(n) auxiliary space
Noncomment Substring Based Elimination - O(n^2) time - O(n) auxiliary space

III. Hashing Apprach

A) Loop over all rotations

1) Bruteforces Algorithm:
  • Iterating over all rotations and comparing for finding the smaller

If they are fully equal, then that position not exceed, then we take the one which smaller index

Else find the first position of character that they are difference, which character is smaller, the which of it is also smaller

Bruteforce Approach - O(n^2 log n) time - O(n) auxiliary space
2) Hashing Improvement:

  • We reduce the complexity by using binary search to find the first different position of two strings:

  • Let $$$A$$$ is the circular substring of $$$s$$$ with the starting point $$$l$$$

  • Let $$$B$$$ is the circular substring of $$$s$$$ with the starting point $$$r$$$

  • Let $$$lcp$$$ (longest common prefix) is the last position that $$$A$$$ and $$$B$$$ equal

  • Let $$$t = s + s$$$, for convention of circular string

  • For every $$$p \leq lcp$$$, we have $$$t[l + p - 1] = t[r + p - 1]$$$

  • For every $$$p > lcp$$$, we have $$$t[l + p - 1] \neq t[r + p - 1]$$$

  • Hence we can use binary search to find $$$lcp$$$

  • Fully equal case is that $$$lcp = n$$$

  • If they are difference, compare $$$t[l + lcp]$$$ with $$$t[r + lcp]$$$

3) Implementations:
Single Hashing Approach - O(n log(MOD)) precalculation - O(n log n) time - O(n) auxiliary space
Multiple Hashing Approach - O(n Sigma(log(MOD))) precalculation - O(n log n * k) time - O(n * k) space
4) Optimization:

  • Hash are so heavy of hidden constant, obviously most by modulo operators, but you can have some tricks to solve it

  • Significant improvement: Declare $$$MOD,\ BASE,\ LIM$$$ as const or constexpr

  • In Single Hash, you can use overflow modulo for significant faster but it is also dangerous in same cases (especially hacking)

  • Replace vector with pre-declared array

  • Replace recursive power function by iterative one

  • Improve time to calculate inverse modulo. You can do it linear but cost more space and modulo operators, so it is better to do like below.

Optimized Bruteforce Approach - O(n^2 log n) time - O(n) auxiliary space
Optimized Single Hashing Approach - O(n + log(MOD)) precalculation - O(n log n) time - O(n) space
Optimized Multiple Hashing Approach - O(n Sigma(log((MOD))) precalculation - O(n log n * k) time - O(n * k) space

2) Logarithm Decomposition

1) Algorithm:

  • Let a candidate to say a starting position that might leed to lexicographically minimum string rotation. Hence we have the initial candidates are $$$0, 1, \dots, |S| - 1$$$

  • Let divide the candidates list into parts of size $$$\approx K$$$ (the final part might have much less). There will be $$$\lceil \frac{N}{K} \rceil$$$ parts.

  • Small iteration: For each parts, we find one smallest circular substring of size $$$K$$$, among all equal circular substrings, pick the one with smallest starting position. Each part will produce only one candidate

  • Big iteration: For $$$\lceil \frac{N}{K} \rceil$$$ next candidates we will find one smallest circular substring of size $$$N$$$, among all equal circular substrings, pick the one with smallest starting position. This will give you the answer

2) Proofs:

  • Let $$$A, B$$$ are the circular substrings start from candidates positions, that $$$|A| = |B|$$$. And let $$$X, Y$$$ are the prefixes of $$$A, B$$$, that $$$|X| = |Y|$$$

  • Since we are comparing in lexicographical order, if $$$X < Y$$$ then it will lead to $$$A < B$$$. Hence by using small iteration we sieved all unoptimal candidates, and reduce $$$N$$$ candidates to $$$\lceil \frac{N}{K} \rceil$$$ candidates only.

3) Complexity:

For small iteration, there are $$$N$$$ candidates, and each candidate are compared with $$$K$$$ lengthed circular substrings using hash. Hence $$$O(N \times log(K))$$$

For big iteration, there are $$$K$$$ candidates, and each candidate are compared with $$$N$$$ lengthed circular substrings using hash. Hence $$$O(\lceil \frac{N}{K} \rceil \times log(N))$$$

The total time complexity is $$$\approx O(N log(K) + \frac{N}{K} log(N))$$$

For optimal purpose, let $$$K \approx \log{N}$$$ the complexity therefore will be only $$$O(N log(log N))$$$

4) Notice:

We are comparing string in circular, you can either use modulo position or duplicated string

Becareful that the real size of string and the duplicated one

5) Implementations:

For convention, let just ignore those obvious not a good code (ugly — complex — stupid code worth nothing to say)

Single Hashing Approach - O(n * log((MOD)) precalculation - O(n log(log n)) time - O(n) space
Multiple Hashing Approach - O(n * Sigma(log((MOD))) precalculation - O(n log(log n) * k) time - O(n * k) space

IV. Sqrt Decomposition

1) Divide candidate list into many parts

1) Algorithm:

  • Let a candidate to say a starting position that might leed to lexicographically minimum string rotation. Hence we have the initial candidates are $$$0, 1, \dots, |S| - 1$$$

  • Let divide the candidates list into parts of size $$$\approx K$$$ (the final part might have much less). There will be $$$\lceil \frac{N}{K} \rceil$$$ parts.

  • Small iteration: For each parts, we find one smallest circular substring of size $$$K$$$, among all equal circular substrings, pick the one with smallest starting position. Each part will produce only one candidate

  • Big iteration: For $$$\lceil \frac{N}{K} \rceil$$$ next candidates we will find one smallest circular substring of size $$$N$$$, among all equal circular substrings, pick the one with smallest starting position. This will give you the answer

2) Proofs:

  • Let $$$A, B$$$ are the circular substrings start from candidates positions, that $$$|A| = |B|$$$. And let $$$X, Y$$$ are the prefixes of $$$A, B$$$, that $$$|X| = |Y|$$$

  • Since we are comparing in lexicographical order, if $$$X < Y$$$ then it will lead to $$$A < B$$$. Hence by using small iteration we sieved all unoptimal candidates, and reduce $$$N$$$ candidates to $$$\lceil \frac{N}{K} \rceil$$$ candidates only.

3) Complexity:

  • For small iteration, there are $$$N$$$ candidates, and each candidate are compared with $$$K$$$ lengthed circular substrings. Hence $$$O(N \times K)$$$

  • For big iteration, there are $$$K$$$ candidates, and each candidate are compared with $$$N$$$ lengthed circular substrings. Hence $$$O(\lceil \frac{N}{K} \rceil \times N)$$$

  • The total time complexity is $$$O(N \times (K + \lceil \frac{N}{K} \rceil))$$$

  • For optimal purpose, let $$$K \approx \sqrt{N}$$$ the complexity therefore will be only $$$O(N \sqrt{N})$$$

4) Notice:

  • We are comparing string in circular, you can either use modulo position or duplicated string

  • Becareful that the real size of string and the duplicated one

5) Implementations:

For convention, let just ignore those obvious not a good code (ugly — complex — stupid code worth nothing to say)

Detail Sqrt Decomposition Solution - O(N√N) time - O(N) auxiliary space
Noncomment Sqrt Decomposition Solution - O(N√N) time - O(N) auxiliary space
Optimized Sqrt Decomposition Solution - O(N√N) time - O(1) auxiliary space

2) Hash Improvement

1) Idea:
  • By using hash for comparing two known substrings $$$X$$$, $$$Y$$$ of equal length $$$D$$$. We can compare them from $$$O(S) \rightarrow O(log(S))$$$ by finding their LCP — Longest Common Prefix and comparing $$$X[lcp]$$$ with $$$Y[lcp]$$$
2) Complexity:
  • The total time complexity is $$$O(N \times log(K) + \lceil \frac{N}{K} \rceil \times log(N)) \approx O(N \times \sqrt{N})$$$ but significant smaller constant (About 2 or/to 3 times faster). But the trade off is more complex code and more space is taken.
3) Optimization:

  • Like the above Hashing approach

  • Use constant modulo

  • Replace vector with array

  • Replace recursive with iterative

  • Quick calculating inverse modulo

4) Implementations:
Single Hash Solution - O(N + log(MOD)) preprocessing - O(N√N) time - O(N) auxiliary space
Single Hash Solution - O(N + Sigma(log(MOD))) preprocessing - O(N√N * K) time - O(N * K) auxiliary space

V. KMP Approach

A) Normal KMP

1) Algorithm:

  • In this problem, there is no effeciency using normal KMP over all pair substring comparing, even if we divide into queries and optimize it. It still have no improvement compare to all other implementations

  • But if you want to compare two strings by KMP, then here it is

  • We find their first different position using KMP of two strings or KMP on concatenation string ($$$s$$$ + $$$c$$$ + $$$t$$$) — for such $$$c$$$ is smaller than any character in $$$s$$$ and $$$t$$$.

2) Implementations:
My Simple KMP Implementations - O(n) time - O(1) auxiliary space
Bruteforces using KMP - O(n^2) time - O(n) auxiliary space

B) Booth Algorithm

1) Idea:
  • Remember when you compare circular substrings using hashing ? We find first difference character $$$k$$$ by binary search and compare only at that position to know whether one is greater, equal or less than other. But this give you huge hidden constant that might lead you TLE (the Optimized version doesnt provides that much but its constant is not that small too). While we can take the advantage of $$$KMP$$$ to find its first difference too, in a much smaller constant ofcourse. But we have to do some clever tricks to ignore its high complexity.
2) Code Explanation:
  • For convention let duplicate the initial string $$$S + S$$$. We can easily find the prefix function for the string. We have to find that at position $$$i > n$$$, which position $$$p$$$ that the initial one and the current rotation differ, then compare the two rotations. However it can only provides comparision between inital rotation and the current rotation, if you want for all rotations you have to merge all $$$N$$$ circular substrings. But, since we only care about the minimal lexicographical, we can just immediately eliminate the worse rotation when you find a better rotation. Then we treat initial rotation by this new better a rotation, but by how can we do that ? The important is that we cut the relationship of the current prefix function with the previous one, by assign the previous as $$$-1$$$, hence we are comparing the prefix function for this current rotation. This allow the algorithm complexity drop from normal KMP $$$O(n^2)$$$ to Booth-KMP $$$O(n)$$$ and way much smaller constant than Hashing $$$O(n log n)$$$.
3)* Implementations:
Detail Booth Algorithm - O(n) time - O(n) auxiliary space
Non-comment Booth Algorithm - O(n) time - O(n) auxiliary space

VI. Lyndon Factorization Approach

A) Approach

1) Definitions:

  • For detail definitions, proves, applications, implementations, you can read Simple Linear and Effectively Duval Algorithm for Lyndon Factorization

  • Lyndon word is nonempty string that is strictly smaller in lexicographic order than all of its rotations.

  • Lyndon factorization is a unique way to split the string into many lyndon words in such a way that the words in the sequence are in non-increasing order. That means we factorize $$$s = s_1 + s_2 + \dots + s_k$$$ where $$$s_1, s_2, \dots, s_k$$$ are lyndon words and in non-increasing order ($$$s1 \geq s2 \geq \dots \geq s_k$$$)

  • From the above definition, we con conclude that the last factor in lyndon factorization of the string itself is minimal lexicographical.

2) Duval Algorithm:
  • In $$$1983$$$, Duval provides an effecient algorithm for listing the Lyndon words of length at most $$$n$$$ with a given alphabet size $$$s$$$ in lexicographic order in $$$O(n)$$$

For string $$$S$$$ of length $$$n$$$

For each new word $$$x$$$ from $$$S$$$ that $$$\forall i$$$ we have $$$x[i] = s[i\ mod\ n]$$$ (mean $$$x$$$ is a sub-string of some cyclic strings that shifted from initial $$$S$$$)

While the last symbol of $$$x$$$ is in sorted order, remove it to make a shorter word

Replace the last remained symbol of $$$x$$$ by its successor in sorted order.

3) Examples:
  • $$$S = $$$"$$$abaabaaabaababaaabaaababaab$$$"
Lyndon Factorization
4) Notice:

  • Wait wait wait, are you going to take the head position of last factor of string factorization and it will be the answer ?

  • Nope, becaure the string are circular, you must duplicate the string before doing so, else there might exist such string that start from from right but connect with left to form a minimal lexicographical string rotation.

5) Implementations:
Detail Duval Solution - O(n) Time - O(n) Auxiliary Space
None-comment Duval Solution - O(n) Time - O(n) Auxiliary Space
6) Optimization:

  • We dont need to duplicate the string

  • We dont need to continue the function when $$$S_2$$$ has the size of $$$n$$$ (or when starting point of $$$S_2$$$ $$$< n \leq$$$ ending point of $$$S_2$$$)

  • We just skip those cases $$$S_2 = s_x + s_x + \dots + s_x + s_y$$$ but jump directly to the next character

Optimized Duval Solution - O(n) Time - O(1) Auxiliary Space

VII. Suffix Array Approach

A) Approach

1) Wrong Idea:
  • Store all suffix of $$$S$$$ (with its index) into an array then sort it (in lexicographical order).

Let $$$S = $$$"$$$baabaa$$$" then there are such suffixes: "$$$a$$$", "$$$aa$$$", "$$$baa$$$", "$$$abaa$$$", "$$$aabaa$$$", "$$$baabaa$$$"

  • Since the first having smallest lexicographical order among all suffixes then its index must be the answer ?
2) Prove it wrong:

  • We are dealing with circular string, and the normal suffix doesnt have enough information.

  • Let $$$A, B$$$ are some different suffixes, and $$$A < B$$$, but if you extend both by size $$$n$$$ then ($$$A < B$$$) might no longer be true, but because of the lexicographical sorting order and all suffixes here having different size, therefore the one with smaller size is considered as "smaller".

3) Correct idea:

  • Sort all suffixes of $$$S + S$$$ with its index

  • Find smallest suffix whose index in $$$0 \dots |s| - 1$$$

  • Compare with other suffixes to find one with smaller index

4) Algorithm:
  • For convention

Let smaller / biggers means in lexicographical order

Let equal means two suffixes have their first $$$n$$$ characters equal (first means prefix of suffix)

Let $$$T = S + S + c$$$ ($$$c$$$ is smaller than any character in $$$S$$$)

  • First we store all suffixes of $$$T$$$ (with its index) into an array then sort it.

  • We can easily find the first suffix $$$X$$$ whose index $$$t$$$ is between ($$$0 \dots n - 1$$$) (those suffixes whose length are at least $$$n$$$)

  • Since there might be some other equal suffixes of size $$$n$$$ whose index is smaller, we compare strings and find it

5) Optimizations:

  • Since all suffixes are sorted and we only need to care smallest suffixes (all among them we select the one with smallest index)

  • Hence we only need to care about consecutive suffixes with $$$X$$$ (they are either bigger than $$$X$$$ or equal to $$$X$$$ but with smaller index)

Let $$$Y$$$ is the current suffix (consecutive to right of $$$X$$$ of course)

If $$$X = Y$$$ then $$$Y$$$ must have smaller index, hence we update the result

Otherwise since $$$Y > X$$$, hence we break

6) Examples:
  • Let $$$SA[]$$$ (Suffix Array) is the array which stores order of suffixes

$$$SA[i] < SA[j]$$$ means suffix start from $$$i$$$ is smaller than suffix start from $$$j$$$

  • Let $$$LCP[]$$$ (Longest Common Prefix) is the array with store the longest common prefix between two consecutive suffixes in the order of $$$SA[]$$$

$$$LCP[x] = k$$$ means suffix start from $$$SA[x]$$$ and $$$SA[x + 1]$$$ have their longest common prefix is $$$k$$$

  • For $$$S = $$$"$$$aaba$$$"
Example
7) Notices:

  • With $$$T = S + S$$$ instead of $$$T = S + S + c$$$, there are actually have plentiful implementations to make algorithm right, even only $$$T = S$$$ there are ways to solve the problem too. But they might much more complex, slow or just correct for this problem that you should be careful.

  • Smallest lexicographical suffix might not have smallest index

8) Implementations:
  • There are many ways to implement suffix array (I wont go deeper)
Spoiler
  • There are many ways to implement longest common prefix: (I wont go deeper)
Spoiler
  • Here are main implementations
Simple Optimized Implementation - O(n log n) SA - O(n) LCP - O(n log n) total time - O(n) auxiliary space

VIII. Suffix Automation Approach

A) Approach

1) Algorithm:

  • Construct Suffix Automaton of $$$s + s$$$. The automaton itself is a path graph of all string rotations

  • Inorder to get lexicographically minimal string rotation, we traverse from initial state $$$|s|$$$ times by smallest edge (in lexicographical order), Let this state is $$$X$$$

  • For inding its index, we find the first occurence of minal strings, equivalence to first occurence of state $$$X$$$. We construct occurences of each state. Let first occurence of state $$$P$$$ is $$$f(P)$$$

  • Let not go deeper in construction here. We have least rotation $$$r = f(X) - |s| + 1$$$

2) Implementations:
Suffix Automaton Solution - O(n log(alphabet)) time - O(n) auxiliary space

IX. Elimination Tournament Algorithm

So here are my other approachs for this problem. I dont know whether there are names for these algorithm. I just got the ideas from soccer elimination and apply to this problem. By self-researching and computing, finaly I archive linear algorithm

About the algorithm name, if one know any paper about it before, please tag me in and I will tag the first authurs of those/these algorithms

The simplest idea is that we have a list of candidate, and keep doing elimination until we have the final champion

A) Dual Elimination

1) Idea:
  • So the ideas is that for the initial candidate list, we will select 2 consecutive candidates, then compare two circular strings of the length equal to the minimum gap of the two candidates
2) Algorithm:
  • Let $$$t = s + s$$$, and the selected candidates are $$$l$$$ and $$$r$$$. For convention, let $$$l < r$$$, then we will compare $$$A$$$ and $$$B$$$, for which $$$A = t[l \dots l+(r-l)-1]$$$ and $$$B = t[r \dots r+(r-l)-1]$$$.

Case 1: $$$A < B$$$, we will select the starting point of $$$A$$$ become the next candidate, it is $$$l$$$

Case 2: $$$A > B$$$, we will select the starting point of $$$B$$$ become the next candidate, it is $$$r$$$

Case 3: $$$A = B$$$, we will select the smaller starting point of $$$A$$$ and $$$B$$$, it is $$$min(l, r)$$$

3) Example:
  • $$$S = $$$"$$$abaabaaabaababaaabaaababaab$$$"
Round I - 27 candidates
Round II - 13 candidates
Round III - 7 candidates
Round IV - 4 candidates
Round V - 2 candidates
Champion
4) Notice:
  • We are comparing circular string !
5) Complexity:

  • Normal Version: Stable Complexity

  • Optimized Version: Linear when characters are unique

  • At the $$$k$$$ elimination, the number of participants will be about $$$O(\frac{n}{2^k})$$$

  • At the $$$k$$$ elimination, each string will be compared $$$O(2^k)$$$ times

  • Hence the total complexity is $$$O(\overset{\lceil log_n \rceil}{\underset{k = 1}{\Sigma}}(\frac{n}{2^k} \times 2^k))$$$ $$$=$$$ $$$O(n \times 1 + \frac{n}{2} \times 2 + \dots + \frac{n}{2^{\lceil log_2(n) \rceil}} \times \lceil log_2(n) \rceil)$$$ $$$=$$$ $$$O(n \times \lceil log_2(n) \rceil)$$$ $$$=$$$ $$$O(n\ log\ n)$$$

6) Implementations:
Detail Dual Elimination Algorithm - O(n log n) time - O(n) auxiliary space
Noncomment Dual Elimination Algorithm - O(n log n) time - O(n) auxiliary space
Optimized and Simple Dual Elimination Algorithm - O(n log n) time - O(n) auxiliary space

B) Substring Based Elimination

1) Idea:
  • From inital set of candidates, keep comparing substrings and eliminate the bigger one until we get the final champion
2) Algorithm:
  • First, let $$$mn$$$ / $$$mx$$$ is the minimal / maximal character of $$$s$$$

Define: $$$mn = \underset{c \in S}{min}(c)$$$ and $$$mx = \underset{c \in S}{max}(c)$$$

  • Pre-elimination Round: We take the position $$$p$$$ that $$$s[p] = mn$$$. Since all other positions wont provide Minimal Lexicographical Circular String

Define: $$$candidate = $$$ { $$$p\ \ |\ \ p \in $$$ { $$$0, 1, \dots, |s| - 1$$$ } $$$ \cap s[p] = mn$$$ }

  • Then we take maximumly $$$n - 1$$$ Rounds from $$$d = 1$$$ to $$$d = n - 1$$$. For all current candidate, add the next character to it. Find the minimal substring, and eliminater unsatisfied others.
3) Optimization

Optimization: At the $$$p$$$ round we will find $$$c = $$$ minimal character among all candidate's $$$pth$$$-next character, then traverse again and eliminate the one whose $$$pth$$$-nxt character is greater than $$$c$$$

Define: $$$s[x] = s[x\ mod\ |s|]$$$ and $$$c = \underset{p \in\ candidate}{min}(s[p + d])$$$ and $$$next\ candidate = $$$ { $$$p\ \ |\ \ p \in candidate \cap s[p + d] = c$$$ }

4) Example:
  • $$$S = $$$"$$$abaabaaabaababaaabaaababaab$$$"
Pre-elimination - 26 candidates
Round I - 18 candidates
Round II - 9 candidates
Round III - 3 candidates
Round IV - 3 candidates
Round V - 3 candidates
Round VI - 2 candidates
Champion
5) Notice
  • After all eliminations, if there are more than one candidate, select the one with lowest index
6) Complexity

  • If the string is $$$k$$$-repeated strings (each substring size $$$d$$$) or similar then there will be atleast $$$k$$$ candidate after $$$d$$$ eliminations. About $$$O(k \times d)$$$ in the best cases

  • Best case to say, like a string where all characters are unique, then it will be Linear $$$O(n)$$$

  • Worst case to say, like a string where all characters are the same, then it will be $$$O(n \times n) = O(n^2)$$$

7) Implementations
  • For convention, let not use obviously-not-optimized code
Detail Substring Based Elimination - O(n^2) time - O(n) auxiliary space
Noncomment Substring Based Elimination - O(n^2) time - O(n) auxiliary space

C) Elimination and Colliding

1) Idea:

  • This is the improvement from Substring Based Elimination. It takes me few hours to think and to implement the idea

  • If two substrings colide then one will be eliminate

2) Algorithm:

  • At the $$$dth$$$ elimination

  • Let $$$s[p] = s[p\ mod\ |s|]$$$ for convention

  • Let $$$l, r$$$ are the candidates and $$$l < r$$$

  • Let $$$A$$$ is a circular substring of $$$s$$$ and $$$A = s[l \dots l + d - 1]$$$

  • Let $$$B$$$ is a circular substring of $$$s$$$ and $$$B = s[r \dots r + d - 1]$$$

  • If $$$A$$$ and $$$B$$$ collide ($$$l + d - 1 = r$$$), we will select $$$l$$$ and eliminate $$$r$$$ (since $$$l < r$$$)

3) Proof:
  • Let $$$A_1, A_2, \dots, A_k$$$ are consecutive circular substring of $$$s$$$ that satisfy

  • $$$\Sigma(|A_i|) = |S|$$$

  • $$$A_i = s[l_1, r_i]$$$

  • $$$l_{i+1} \equiv r_i + 1$$$ (mod $$$n$$$)

  • No loss of generality. Let $$$A_1$$$ and $$$A_2$$$ are the substring we are comparing, for such $$$l1, l2$$$ are the candidates, then we also have $$$l_1 = min(l_i)$$$

  • In lexicographical order (in comparing the strings) to say

If $$$A_1 < A_2$$$ then $$$l_2$$$ will be eliminated

If $$$A_1 > A_2$$$ then $$$l_1$$$ will not be the next candidate

If $$$A_1 = A_2 = \dots = A_k$$$ then $$$min(l_i)$$$ will be the champion. Hence $$$l_1$$$ is

Else there is such $$$p$$$ that $$$A_1 = A_2 = \dots = A_p \neq A_{p+1}$$$

  • There is only the case $$$A_p < A_{p+1} \Rightarrow A_1A_2\dots A_p < A_2A_3 \dots A_{p+1}$$$, hence $$$l_2$$$ will be eliminated

  • Because for this case $$$A_1 = A_2 = A_p > A_{p+1}$$$ — the contradiction happened where $$$l_1, l_2, \dots, l_p$$$ are all candidates (Since $$$A_1 = A_2 = \dots = A_p$$$), but $$$A_{p+1}$$$ is smaller ($$$l_{p+1}$$$ should be the candidate instead

  • Let $$$p_1, p_2, \dots, p_k$$$ the candidates and $$$A_1, A_2, \dots, A_k$$$ the candidate circular substrings of $$$s$$$ that start from those position

$$$S = aabaaa\dots$$$ and $$$A_1 = aab$$$, $$$A_2 = aaa$$$ then $$$A_1$$$ is eliminated, $$$p_2 = 3$$$ the next candidate

$$$S = aabaac\dots$$$ and $$$A_1 = aab$$$, $$$A_2 = aac$$$ then $$$A_2$$$ is eliminated, $$$p_1 = 0$$$ the next candidate

$$$S = aabaabaab\dots aab$$$ and $$$A_1 = A_2 = \dots = A_k = aab$$$, then $$$p_1 = 0$$$ the champion

$$$S = aabaabaab\dots aabaac\dots$$$ and $$$A_1 = A_2 = \dots = A_p = aab \neq A_{p+1} = aac$$$, then $$$p_1 = 0$$$ the next candidate

$$$S = aabaabaab\dots aabaaa\dots$$$ and $$$A_1 = A_2 = \dots = A_p = aab \neq A_{p+1} = aaa$$$, then contradiction happened since $$$aaa$$$ should be the candidate instead

4) Example:
  • $$$S = $$$"$$$abaabaaabaababaaabaaababaab$$$"
Pre-elimination - 26 candidates
Round I - 18 candidates
Round II - 6 candidates
Round III - 3 candidates
Round IV - 2 candidates
Round V - 2 candidates
Round VI - 2 candidates
Champion
5) Notice:
  • Collision Detecting is on Circular Substring
6) Complexity:

If the string continues to grown, then they will collide and dies

Trying to extend string size $$$k$$$ mean minimize candidate list size $$$O(k \times \lfloor \frac{n}{k} \rfloor) = O(n)$$$

Trying to maximize candidate list size $$$k$$$ mean reduce the string size $$$O(f(x)) = O(k \times (\lfloor \frac{n}{k} \rfloor \times k - k)) + O(f(\lfloor \frac{k}{2} \rfloor)) = O(k\ log\ k)$$$

7) Implementations:
  • For convention, let not use obviously-not-optimized code
Detail Elimination and Colliding - O(n log n) time - O(n) auxiliary space
Elimination and Colliding - O(n log n) time - O(n) auxiliary space

D) Elimination and Merging

1) Idea:

  • This is the improvement from Elimination and Colliding. It takes me few days to think, to prove and to implement the idea

  • If many substrings collide, we can eliminate all as once. And jump directly to the1

  • From the above proof, we also have the property that when $$$p$$$ is one of the candidates then $$$repeated-string$$$ start from $$$p$$$ might be one of the candidate

2) Algorithm:

  • At the $$$dth$$$ elimination, let $$$p_1, p_2, \dots, p_k$$$ are the candidates, $$$A_1, A_2, \dots, A_k$$$ are circular substring of $$$s$$$ that $$$A_1 = s[p_1 \dots p_1 + d - 1]$$$. Notice that all of them are either collide ($$$p_i + d - 1 \equiv p_{i+1}$$$ (mod $$$n$$$)) or not intersect (because the intersect pairs are eliminated at their first collision)

  • Let $$$v$$$ is the maximum collision or/and exist such consecutive candidates $$$q_1, q_2, \dots, q_v$$$ that $$$A_{q_1}$$$ collides $$$A_{q_2}$$$ collides $$$\dots$$$ collides $$$A_{q_v}$$$. Then $$$A_{q_1}A_{q_2} \dots A_{q_v}$$$ is the best candidates up to the $$$(d \times v)$$$-th elimination.

  • Therefore, instead of eliminating all the weaker candidates, we can just merge them and teleport to the next elimination that they collides again

3) Proofs:

  • I think you can prove this based on Elimination and Colliding and Duval Lyndon Approach.

  • Good thing is that this will also prove the linear complexity of the algorithm

4) Example:
  • $$$S = $$$"$$$abaabaaabaababaaabaaababaab$$$"
Pre-elimination - 26 candidates
Round III - 3 candidates
Champion
5) Notice:

  • If the candidates arent changed, teleport to next tournament not itself

  • The last candidate might merge with the first candidate

  • When merging, you should use modulo operator for safety

  • Because of its complex code, you can just ignore pre-elimination and play round $$$d = 1$$$ to $$$n$$$

6) Complexity:

It seem to be about $$$O(n\ log\ n)$$$ when each time the candidates is eliminate atleast a half

But actually the complexity is Linear $$$O(n)$$$ because every position is called maximumly once for preprocessing, twice times for comparings, thrice for merging only.

7) Implementations:
Detail Elimination and Merging - O(n) time - O(n) auxiliary space
Noncomment Elimination and Merging - O(n) time - O(n) auxiliary space
8) Optimization
  • Since every position $$$p$$$, will in range $$$0 \dots 2 \times n - 1$$$, hence we can precalculate the modulo of each
Optimized Elimination and Merging - O(n) time - O(n) auxiliary space
  • Vote: I like it
  • +106
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Quick question: Why do you have so much whitespace in the blogs? Is there any reason for this?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    To the benefit of codeforces.

    Spoiler
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually since all titles, headers, subheaders have their own font sizes. Without the gaps the contents will be densed and hard for reading and you might have eye-ache. Therefore the larger the font size is, I must leave some gaps between them

    Also for editting purpose, I am actually using spaces or break lines but they only work for the editor.That why I use cutline in order to make gaps

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the other hand, arent the gaps make you easier to read, search, know which contents belong to which headers, and your eyes be free when the text are sparsed enough? UwU

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      No, they are a nuisance to me at least. I have to scroll through that much whitespace just to see a few lines of text. At least to me, they are pretty annoying.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, currently for my blog:

        • It is 50/10 cut lines for red titles

        • It is 10/2 cut lines for green headers

        • It is 1/0 cut line for dark-cyan sub-headers

        Do you have any recommendation ?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Honestly, all you need to do is just press Enter every time you begin a new section. https://codeforces.com/blog/entry/61290 Here's one blog with this kind of formatting.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I dont like when the editorial are too dense.

            • You hard to find headers, titles and might confuse when read to fast, or read a mixture of some bold texts and bold headers

            • Your eyes must working harder to receive and analyze more information from dense words then sparse one

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should also try to include references.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Well except KMP-Booth and Lyndon-Duval Algorithms, all are my own implementations, hence I only have some papers about KMP-Booth and Lyndon-Duval only

    → Reply
»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

In III. Hashing Approach A1, I see, you gave condition over lcp is equal to n or not. It is always false. Can you check please?

Screenshot of the Code Snippet

→ Reply