// Arup Guha
// 4/6/2010
// for 2008 AP Free Response Question #2: String Encoding and Decoding

import java.util.*;

public class StringCoder {
	
	// This was given to us.
	private String masterString;
	
	public StringCoder(String master) {
		masterString = master;
	}
	
	// Solution to part (a)
	public String decodeString(ArrayList<StringPart> parts) {
		
		// Start with nothing.
		String ans = "";
		
		// Go through each part.
		for (int i=0; i<parts.size(); i++)
			
			// You have to be careful with the syntax of extracting each part.
			// substring takes different parameters that just start and length.
			ans = ans + masterString.substring(parts.get(i).getStart(), 
						parts.get(i).getStart()+parts.get(i).getLength());
											   
		return ans;
	}
	
	// Not part of the solution, but necessary to check the solution. For the
	// test, you simply assume this works.
	private StringPart findPart(String str) {
		
		int max = 0;
		int start=0, len=0;
		
		// i represents the start of the match in the masterString
		for (int i=0; i<masterString.length(); i++) {
			
			// j represents the index into the string str.
			int j = 0;
			int savei = i;
			while (savei<masterString.length() && j<str.length() &&
				   masterString.charAt(savei) == str.charAt(j)) {
				   
				savei++;   
			    j++;
			}
			
			// This will trigger at least once, since we're guaranteed
			// by the pre-condition that there will be at least one match.
			if (j > max) {
				
				// Save the start and length of this match.
				start = savei-j;
				len = j;
				
				// Now we have a new match of maximum length.
				max = j;
			}	
				
		}
		
		// This is the longest match we found.
		return new StringPart(start, len);
	}
	
	// Solution to part (b).
	public ArrayList<StringPart> encodeString(String word) {
		
		// Start with no parts.
		ArrayList<StringPart> ans = new ArrayList<StringPart>();
		
		// Keep on going until the whole word has been encoded.
		while (word.length() > 0) {
			
			// Get the next part.
			StringPart next = findPart(word);
			int len = next.getLength();
			
			// Chop off this part from the string to encode.
			word = word.substring(len);
			
			// Add this to our array list.
			ans.add(next);
		}
		
		return ans;
	}
	
	public static void main(String[] args) {
		
		StringCoder s = new StringCoder("sixtyzipperswerequicklypickedfromthewovenjutebag");
		
		ArrayList<StringPart> theseparts = s.encodeString("overeager");
		
		// Print out encoding
		for (int i=0; i<theseparts.size(); i++)
			System.out.println(theseparts.get(i));
			
		String answer = s.decodeString(theseparts);
		System.out.println("Decoded strng is "+answer);
			
	}
}