Calculating Garland Degree of String

Purpose

A garland word is a word

formed by chopping off the last few letters and “wrapping around” to the start.

For example: You can chop off the the trailing “on” from “onion” and still form the word by wrapping around to the starting “on”. In other words, you can write the letters “o”, “n”, “i” in a circle, in that order, and form the word “onion”.

I say that a garland word is of degree n if you can do the above with the last n letters of the word.

Build an implementation that returns the garland degree of a String. (Note, this was a dailyprogrammer subreddit question)
Strategy

• Check if String is size 0 (return garland degree of 0) or size 1 (return garland degree of 1).

• Start with the first character in the String. Iterate through the characters in the String from the second character onwards. Do we see a matching character? If not, return size 0.

• Move on to the first + second characters in the String. Iterate through the characters in the String from the 3rd character onwards for a matching substring - if we can't see one, return size 1.

• Repeat.

• Note that the upper limit of the garland degree should be the the floor of the length of the String divided by 2. (Right? Or am I missing something?)

Implementation
`public class GarlandDegreeIdentifierImpl implements GarlandDegreeIdentifier {
@Override
public int identifyGarlandDegree(final String candidate) {
switch (candidate.length()) {
case 0: {
return 0;
}

case 1: {
return 1;
}

default: {
final char[] chars = candidate.toCharArray();
for (int subStringIndex = 1; subStringIndex

You are completely over-doing it. Your algorithm will be O(n3) (I think) on the length of the input when you can do it more simply in O(n2).

Consider the following instead:

• Start at the middle of the input.

• While the substring starting from this index is not equal the substring beginning the start of the input with the same length, we increment the index.

• Finally, we return the length of the final substring that matched.

Basically, the logic can be summed up by this drawing:

-------------
^^^^^^ ^^^^^^ matches or not?

// if no continue

-------------
^^^^^ ^^^^^ matches or not?

// if no continue

-------------
^^^^ ^^^^ matches or not?


You can see the logic.

Implemented in code, it would be the following:

private static int identifyGarlandDegree(String candidate) {
    int length = candidate.length();
    int index = length / 2;
    while (!candidate.substring(0, length - index).equals(candidate.substring(index))) {
        index++;
    }
    return length - index;
}

Note that we don't need to add a check on index: it won't go out of bounds since when index == length, it will exit normally (empty string being equal to another empty string).

StackExchange Code Review Q#119117, answer score: 5