/*
 * File: FrontCodingCompression.java
 * ---------------------------------
 * This program implements Front Coding to compress
 * representing two strings.
 */

import acm.program.*;
import acm.util.*;
import java.awt.*;

public class FrontCodingCompression extends ConsoleProgram {
	
	public void run() {
		println(frontCoding("automate", "automaton"));
		println(frontCoding("are", "area"));
		println(frontCoding("cat", "dog"));
	}
	
	/*
	 * frontCoding
	 * -----------
	 * Applies the front coding algorithm to the two given
	 * strings; returns the single compressed string.
	 * Algorithm for front coding:
	 * 
	 * length of prefix + prefix + "*" + length of suffix 1 + suffix 1 + length of suffix 2 + suffix 2
	 */
	private String frontCoding(String str1, String str2) {
		// get the index of the first character where the two strings differ
		int endIdx = 0;
		for (int i = 0; i < str1.length(); i++) {
			if (str1.charAt(i) != str2.charAt(i)) {
				break;
			} else {
				endIdx++;
			}
		}
		
		// the two strings have a common prefix up until (but excluding) endIndex
		String prefix = str1.substring(0, endIdx);
		
		// extract suffixes
		String suffix1 = str1.substring(endIdx);
		String suffix2 = str2.substring(endIdx);
		
		return prefix.length() + prefix + "*" + suffix1.length() + suffix1 + suffix2.length() + suffix2;
	}
	
}
