CODEWITHSUNDEEP
stringalgorithm
Mod
Mod

Reputation: 383

Number of distinct rotated strings

We have a string S and we want to calculate the number of distinct strings that can be formed by rotating the string.

For example :-

S = "aaaa" , here it would be 1 string {"aaaa"}

S = "abab" , here it would be 2 strings {"abab" , "baba"}

So ,is there an algorithm to solve this in O(|S|) complexity where |S| is the length of string.

Upvotes: 2

Views: 2294

Answers (3)

Jacob
Jacob

Reputation: 34621

You can solve this with rolling hash functions used in the Rabin-Karp algorithm.

You can use the rolling hash to update the hash table for all substrings of size |S| (obtained by sliding a |S| window across SS) in constant time (so, O(|S|) in total).

Assuming your string comes from an alphabet of constant size, you can inspect the hash table in constant time to obtain the required metric.

Upvotes: 2

ukkonen
ukkonen

Reputation: 66

Suffix trees, baby!

If string is S. Construct the Suffix Tree for SS (S concatenated to S).

Find number of unique substrings of length |S|. The uniqueness you get automatically. For length |S| you might have to change the suffix tree algo a little (to maintain depth info), but is doable.

(Note that the other answer by johnsoe is actually quadratic, or worse, depending on the implementation of Set).

Upvotes: 5

johnsoe
johnsoe

Reputation: 674

Something like this should do the trick. 

public static int uniqueRotations(String phrase){
    Set<String> rotations = new HashSet<String>();
    rotations.add(phrase);
    for(int i = 0; i < phrase.length() - 1; i++){
        phrase = phrase.charAt(phrase.length() - 1) + phrase.substring(0, phrase.length() - 1); 
        rotations.add(phrase);
    }
    return rotations.size();
}

Upvotes: 1

Related Questions