Repeating substring

Q: Given a string S find the smallest sub-string X such that S = (X)+, i.e. S is a repetition of one or more X's.

Soln approach: 

• Iterate string from start to end keeping 2 pointers pointing to certain indexes in the string
• The first one indicating endIndex of the sub-sequence X found till now
• The second one indicating the index with which we must compare the character read in the next iteration
• Update both the indexes in each iteration based on whether the character read matches the sub-sequence 
• At the end X will be the sub-string from 0 to the first index mentioned in first point above

Java code:

	/**
	* Author: Varun
	* Date: Jun 5, 2012
	*/
	public class XPlusPatternMatcher {
	// returns X of regex (X)+
	public static String match(String str) {
	if(str == null || str.length() == 0) {
	return "";
	}
	char[] chars = str.toCharArray();
	int subsequenceEndIndex = 0;
	int nextCharMatchIndex = 0;
	for(int i = 1; i < chars.length; i++) {
	if(chars[nextCharMatchIndex] != chars[i]) {
	subsequenceEndIndex = i;
	nextCharMatchIndex = 0;
	} else {
	nextCharMatchIndex += 1;
	if(nextCharMatchIndex > subsequenceEndIndex) {
	nextCharMatchIndex = 0;
	}
	}
	}
	return str.substring(0, subsequenceEndIndex + 1);
	}
	public static void main(String[] args) {
	String testString = "abcdeabcdefabcdeabcdef";
	System.out.println(match(testString));
	}
	}

view raw XPlusPatternMatcher.java hosted with ❤ by GitHub