Algorithm

USACO Section5.5 Hidden Password (hidden)

Problem Summary

Given a string S composed of L (5<=L<=100,000) letters, find the start position of the first letter of the sorted list of cyclic shifts of S.

For example, with the string “alabala”, the sorted cyclic shifts are:

aalabal
abalaal
alaalab
alabala
balaala
laalaba
labalaa

Lexicographically, the first string is “aalabal”. So the answer is position 6.

Solution

First, we concatenate two copies of our string S, yielding SS. Then we simply want the lexicographically least L-letter substring of SS.

We use two iterators to indicate the two positions we are comparing. Let i be 0 and j be 1, and start a while loop. Each time, suppose k is the minimal non-negative integer s.t. s[i+k]!=s[j+k] && k<=L. Then there are 4 cases:

  1. i or j is equal to or greater than L. Then the smaller one is answer.
  2. k does not exist, i.e. the L-letter substring starting at i is the same as the one starting at j. We move j to j+L.
  3. s[i+k]>s[j+k]. In this case, it is needless to examine the substrings starting at i, i+1, i+2,…, or i+k. So we just move i to i+k+1.
  4. s[i+k]<s[j+k]. Similarly, we move j to j+k+1.

Apparently, the time comlexity is O(n).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
const int maxn = 200020;
int n;
char s[maxn];
int main()
{
	fstream fin("hidden.in",ios::in);
	fstream fout("hidden.out",ios::out);
	fin>>n;
	for(int i=0;i<n;i+=72)
		fin>>(s+i);
	for(int i=0;i<n;i++)
		s[i+n]=s[i];
	int i=0,j=1,k;
	while(i<n && j<n)
	{
		k=0;
		while(k<n && s[i+k]==s[j+k])
			k++;
		if(s[i+k]>s[j+k])
			i+=k+1;
		else
			j+=k+1;
		if(i==j) j++;
	}
	if(i>j) i=j;
	fout<<i<<endl;
	fin.close();
	fout.close();
	return 0;
}