/**
   This class implements the elementary algorithms on words
   of Section 1.2.
   These include string-matching algorithms, subwords with
   longest common subwords and conjugacy with minimal
   cyclic conjugate and Lyndon factorization. Usage:<br>
   <code>java ElementaryAlgorithms command word1 (opt) word2</code><br>
   where <code>command</code> can be one of<br>
   <code>border</code> to print the border array of <code>word1</code><br>
   <code>borderSharp</code> to print the sharp border array 
   of <code>word1</code><br>
   <code>circularMin</code> to print the least conjugate 
   of <code>word1</code><br>
   <code>lyndonFact</code> to print the Lyndon factorization 
   of <code>word1</code><br>
   <code>lcsArray</code> to print the array of lengths of the longest
   common subwords of  <code>word1</code> and <code>word2</code><br>
   <code>lcs</code> to print a longest
   common subword of  <code>word1</code> and <code>word2</code><br>
   For example, the command<br>
   <code>java ElementaryAlgorithms border abracadabra</code><br>
   produces the output<br>
   <code>-1 0 0 0 1 0 1 0 1 2 3 4</code><br>
   The command<br>
   <code>java ElementaryAlgorithms circularMin abracadabra</code><br>
   produces<br>
   <code>aabracadab</code><br>
   The command<br>
   <code>java ElementaryAlgorithms lyndonFact abracadabra</code><br>
   produces<br>
   <code>0</code><br>
   <code>7</code><br>
   <code>10</code><br>
   <code>(abracad)(abr)(a)</code><br>
   The command<br>
   <code>java ElementaryAlgorithms lcs abracadabra arbadacarba</code><br>
   produces<br>
   <code>aradara</code><br>



*/
public class ElementaryAlgorithms{
    /**
       Implements the algorithm  <code>Border(x)</code> of Section 1.2.2.
       The border of a nonempty word <code>x</code>
       is the longest proper prefix of <code>x</code> which is also
       a suffix of <code>x</code>.
       Complexity: linear in the length of <code>x</code>. Actually,
       the number of comparisons is at most <code>2*|x|</code>.
       @return the array <code>b[]</code> of border lengths, where
       <code>b[i]</code>
       is the length of the border of <code>x[0..i-1]</code>
    */
    public static int[] border(String x) {
	
	int i = 0;
	int j;
	int m=x.length();
	int[] prefixes=new int[m+1];
	prefixes[0] = -1;
	for (j = 1; j < m; j++) {
	    prefixes[j] = i;
	    while(i >= 0 && x.charAt(j) != x.charAt(i))
		i = prefixes[i];
	    i++;
	}
	prefixes[m] = i;
	return prefixes;
    }
    static void print(int[] b){
	for(int i = 0; i < b.length; i++)
	    System.out.print(b[i]+" ");
	System.out.println();
    }
    /**
       Implements the algorithm <code>BorderSharp(x)</code> of Problem 1.2.1.
       Complexity: linear in <code>|x|</code>.
       @return the sharp border array of <code>x</code>. For a word 
       <code>x</code> of length <code>m</code>, <code>sb[m]=b[m]</code>
       and for <code>1<=j<=m-1</code>, <code>sb[j]</code> is the largest
       integer <code>i</code> such that <code>x[0..i-1]=x[j-i..j-1]</code>
       and <code>x[j]!=x[i]</code>.
    */
   public static int[] borderSharp(String x) {

       int i, j;
	int m = x.length();
	int[] sharpPrefixes = new int[m+1];
	sharpPrefixes[0] = -1;
	i = 0;
	for (j = 1; j <= m - 1; ++j) {
	    /* Here, x[0..i - 1] = Border(x[0..j - 1])*/
	    if (x.charAt(j) == x.charAt(i))
		sharpPrefixes[j] = sharpPrefixes[i];
	    else {
		sharpPrefixes[j] = i;
		do {
		    i = sharpPrefixes[i];
		}
		while (i >= 0 && x.charAt(j) != x.charAt(i));
	    } 
	    ++i;
	} 
	sharpPrefixes[m] = i;
	return sharpPrefixes;
    }
    /**
       Implements the algorithm <code>CircularMin()</code>
       of Section 1.2.5.
       Complexity: linear in <code>|x|</code>.
       @return the index <code>k</code> such that <code>x[k..k-1]</code>
       is the least conjugate of <code>x</code>.
    */
   public static int circularMin(String x) {
	int i, j, k;
	int m = x.length();
	int[] b = new int[2*m+1];
	i = 0; k = 0; j = 1;
	b[0] = -1;
	while (k+j < 2*m) {
	    if(j-i == m) break;
	    b[j] = i;
	    while (i >= 0 && x.charAt((k+j)%m ) != x.charAt((k+i)%m )){
		if(x.charAt((k+j)%m) < x.charAt((k+i)%m))
		    { k += j-i; j = i; }
		i = b[i];
	    }
	    ++i;++j;
	}
	return k;
    }
    /**
       Returns the least conjugate of <code>x</code>.
    */
    public static String minConjugate(String x){
	int k = circularMin(x);
	return x.substring(k) + x.substring(0,k);
    }
    /** 
	Implements the function <code>LyndonFactorization()</code>
	of Section 1.2.5.
	Complexity: <code>O(|x|)</code>.
	@return the longest prefix of <code>x</code> which is  a Lyndon word
	and its exponent in the factorization of <code>x</code>. 
    */
    public static int[] lyndonFactorization(String x) {
	int i = 0, j = 1;
	int[] pair = new int[2];
	int m = x.length();
	while (j < m && x.charAt(i) <= x.charAt(j)) {
	    i = (x.charAt(i) < x.charAt(j)) ? 0 : i+1;
	    j++;
	}
	pair[0] = j-i;
	pair[1] = j/(j-i);
	return pair;
    }
    /**
       The same as <code>lyndonFactorization</code>
       concerning <code>x[k..]</code>.
    */
    public static int[] lyndonFactorizationR(String x, int k) {
	int i = k, j = k + 1;
	int[] pair = new int[2];
	int m = x.length();
	while (j < m && x.charAt(i) <= x.charAt(j)) {
	    i = (x.charAt(i) < x.charAt(j)) ? k : i + 1;
	    j++;
	}
	pair[0] = j - i;
	pair[1] = (j - k) / (j - i);
	return pair;
    }
    /**
       Returns the Lyndon factorization of the word <code>x</code>
       in the form <code>(fact1)(fact2)...</code>.
       Complexity: <code>O(|x|)</code>.
    */
    public static String lyndonFact(String x){
	int k=0;
	String s = new String();
	while(k < x.length()){System.out.println(k);
	    int[] pair = lyndonFactorizationR(x, k);
	    String f = x.substring(k, k + pair[0]);
	    for(int e = 0; e < pair[1]; e++)
		s += "(" + f + ")";
	    k = k + pair[0]*pair[1];
	}
	return s;
    }
    /**
       Implements the algorithm <code>NaiveStringMatching(x,y)</code>
       of Section 1.2.3.
       Complexity: <code>O(|x|*|y|)</code>.
       @return true if <code>x</code> is a factor of <code>y</code>.
    */
    public static boolean naiveStringMatching(String x, String y){
	int i = 0,j = 0,m = x.length(),n = y.length();
	do{
	    if(x.charAt(i) == y.charAt(j)){
		i++; j++;
	    }
	    else{
		j = j-i+1;
		i = 0;
	    }
	}while(i<x.length() && j<y.length());
	return i==m;
    }
    /**
       Implements the algorithm <code>Searchfactor(x,y)</code>
       of Section 1.2.3.
       Complexity: <code>O(|x|+|y|)</code>.
       @return true if <code>x</code> is a factor of <code>y</code>.
    */
    static boolean searchFactor(String x, String y) {
	int i = 0, j = 0;
	int m = x.length(), n = y.length();
	/*b is the array of borders of the prefixes of x*/
	int[] b = border(x);
	while (i < m && j < n) {
	    while (i >= 0 && x.charAt(i) != y.charAt(j))  
		i = b[i];
	    i++; j++;
	}
	return i == m;
    }
    /**
       Implements the algorithm <code>LongestCommonPrefix()</code>
       of Section 1.2.1.
       @return the length of the longest common prefix of 
       <code>x</code> and <code>y</code>.
    */
     public static int longestCommonPrefix(String x,String y){
	int i;
	int n = Math.min(x.length(), y.length());
	for(i = 0;i < n && x.charAt(i) == y.charAt(i); i++);
	return i; 
    }
    /**
       Implements the algorithm <code>IsSubword()</code> of Section 1.2.4.
       Complexity: Complexity: <code>O(|y|)</code>.
       @return true if <code>x</code> is a subword of <code>y</code>.
    */
    public static boolean isSubword(String x, String y){
	int i = 0,j = 0;
	while(i < x.length() && j < y.length()){
	    if(x.charAt(i) == y.charAt(j))
		    i++;
	j++;
	}
	return (i == x.length());
    }
    /**
       Computes the length of a longest common subword of <code>x</code>
       and <code>y</code>.
       Complexity: <code>O(|x|*|y|)</code>.
    */
    public static int lcsLength(String x, String y){
	int m = x.length(); int n = y.length();
	int[][] M = new int[m+1][n+1];
	for(int i = 0;i<m;i++)
	    for(int j = 0;j<n;j++)
		if(x.charAt(i) == y.charAt(j))
		    M[i+1][j+1] = M[i][j]+1;
		else
		    M[i+1][j+1] = Math.max(M[i+1][j],M[i][j+1]);
	return M[m][n];
    }
    /**
       Implements the algorithm <code>LcsLengthArray()</code> of Section 1.2.4.
       Complexity: <code>O(|x|*|y|)</code>.
       @return the array <code>M[i][j]</code> giving the length of a
       longest common subword of <code>x[0..i-1]</code> and
       <code>y[0..j-1]</code>.
    */
    public static int[][] lcsLengthArray(String x, String y){
	int m = x.length(); int n = y.length();
	int[][] M = new int[m+1][n+1];
	for(int i = 0;i < m;i++)
	    for(int j = 0;j<n;j++)
		if(x.charAt(i) == y.charAt(j))
		    M[i+1][j+1] = M[i][j]+1;
		else
		    M[i+1][j+1] = Math.max(M[i+1][j],M[i][j+1]);
	return M;
    }
    /**
       Implements the algorithm <code>LCS()()</code> of Section 1.2.4.
       Complexity: <code>O(|x|*|y|)</code>.
       @return a longest common subword of <code>x[0..i-1]</code> and
       <code>y[0..j-1]</code>.
    */
    public static String lcs(String x, String y){
	int i,j,k;
	int m = x.length(), n = y.length();
	int[][] M = lcsLengthArray(x,y);
	String w = new String();
	i = m-1; j = n-1; k = M[m][n]-1;
	while(k >= 0)
	    if (x.charAt(i) == y.charAt(j)){
		w += x.charAt(i);
		k--; i--; j--;
	    }
	    else{
		if (M[i+1][j]<M[i][j+1]) i--;
		else j--;
	    }
	return w;
    }

    static void print(int[][] M){
	for(int i=0;i<M.length;i++){
	    for(int j=0;j<M[i].length;j++)
		System.out.print(M[i][j]);
	    System.out.println();
	}
    }

  static String usage() {
    StringBuilder sb = new StringBuilder("usage : java ");
    sb.append("ElementaryAlgorithms algo data1 [data2]\n");
    sb.append("algo = border, borderSharp, circularMin, lyndonFact ");
    sb.append("lcsArray lcs \n");
    sb.append("data1 and data2 are strings.\n");
    return sb.toString();
  }


    public static void main(String[] args){ 
     if (args.length == 0) {
	System.out.println(usage());
	return;
      }
	if(args[0].equals("border"))
	   print(border(args[1]));
	if(args[0].equals("borderSharp"))
	   print(borderSharp(args[1]));
	if(args[0].equals("circularMin"))
	    System.out.println(minConjugate(args[1]));
	if(args[0].equals("lyndonFact"))
	    System.out.println(lyndonFact(args[1]));
	if(args[0].equals("lcsArray"))
	    print(lcsLengthArray(args[1], args[2]));
	if(args[0].equals("lcs"))
	    System.out.println(lcs(args[1], args[2]));
    }
}