import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
public class main {


public static void main(String[] args) throws Exception {
  Predictor p = new Predictor();
  String s = "hello hello ";
  int score = 0;
  for (int i = 0; i <= l(s); i++) {
    String x = s.substring(0, i);
    char c = p.predict(x);
    boolean correct = i < l(s) && s.charAt(i) == c;
    print((correct ? '*' : ' ') + " " + quote(x) + " => " + quote(c));
    if (correct)
      ++score;
  }
  print("Score: " + score + "/" + l(s));
}

static class Predictor {
    private TreeMap < Character, LinkedList < Integer >> tree = new TreeMap < Character, LinkedList < Integer >> ();
    private int longestMatch = -1;
    /**
     * @return predicted next character of the string
     */
    public char predict(String str) {
        if (str.length() == 0)
            return '0';
        if (str.length() == 1) {
            longestMatch = 0;
            return str.charAt(0);
        }
        if (tree.containsKey(str.charAt(str.length() - 1))) {
            longestMatch++;
            LinkedList < Integer > pred = tree.get(str.charAt(str.length() - 1));
            tree.clear();
            for (int pos: pred) {
                char c = str.charAt(pos + 1);
                LinkedList < Integer > temp;
                if (tree.containsKey(c))
                    temp = tree.get(c);
                else
                    temp = new LinkedList < Integer > ();
                temp.add(pos + 1);
                tree.put(c, temp);
            }
        } else {
            longestMatch = -1;
            int m = 1;
            int i = 0;
            int[] table = createTable(str);
            while (m + i < str.length()) {
                if (str.charAt(str.length() - i - 1) == str.charAt(str.length() - (m + i) - 1))
                    i++;
                else {
                    insertPrediction(str.charAt(str.length() - m), i, str.length() - m);
                    m = m + i - table[i];
                    if (table[i] >= 0)
                        i = table[i];
                }
            }
            if (i > 0)
                insertPrediction(str.charAt(str.length() - m), i, str.length() - m);
        }
        char prediction = '0';
        int maxCount = 0;
        Iterator < Character > it = tree.keySet().iterator();
        while (it.hasNext()) {
            char key = it.next();
            int count = tree.get(key).size();
            if (count > maxCount) {
                prediction = key;
                maxCount = count;
            }
        }
        return prediction;
    }
    private void insertPrediction(char c, int i, int pos) {
        if (i > longestMatch) {
            tree.clear();
            longestMatch = i;
        }
        if (i < longestMatch)
            return;
        LinkedList < Integer > pred = null;
        if (tree.containsKey(c))
            pred = tree.get(c);
        else
            pred = new LinkedList < Integer > ();
        pred.add(pos);
        tree.put(c, pred);
    }
    private int[] createTable(String str) {
        int pos = 2;
        int cnd = 0;
        int[] table = new int[str.length() - 1];
        table[0] = -1;
        while (pos < str.length() - 1) {
            if (str.charAt(str.length() - pos) == str.charAt(str.length() - cnd - 1)) {
                table[pos] = cnd + 1;
                pos++;
                cnd++;
            } else if (cnd > 0)
                cnd = table[cnd];
            else {
                table[pos] = 0;
                pos++;
            }
        }
        return table;
    }
}

static volatile StringBuffer local_log = new StringBuffer(); // not redirected
static volatile StringBuffer print_log = local_log; // might be redirected, e.g. to main bot

// in bytes - will cut to half that
static volatile int print_log_max = 1024*1024;
static volatile int local_log_max = 100*1024;

static void print() {
  print("");
}

// slightly overblown signature to return original object...
static <A> A print(A o) {
  String s = String.valueOf(o) + "\n";
  StringBuffer loc = local_log;
  StringBuffer buf = print_log;
  int loc_max = print_log_max;
  if (buf != loc && buf != null) {
    print_append(buf, s, print_log_max);
    loc_max = local_log_max;
  }
  if (loc != null) 
    print_append(loc, s, loc_max);
  System.out.print(s);
  return o;
}

static void print(long l) {
  print(String.valueOf(l));
}

static void print_append(StringBuffer buf, String s, int max) {
  synchronized(buf) {
    buf.append(s);
    max /= 2;
    if (buf.length() > max) try {
      int newLength = max/2;
      int ofs = buf.length()-newLength;
      String newString = buf.substring(ofs);
      buf.setLength(0);
      buf.append("[...] ").append(newString);
    } catch (Exception e) {
      buf.setLength(0);
    }
  }
}
  static String quote(String s) {
    if (s == null) return "null";
    return "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"").replace("\r", "\\r").replace("\n", "\\n") + "\"";
  }
  
  static String quote(long l) {
    return quote("" + l);
  }
  
  static String quote(char c) {
    return quote("" + c);
  }

static int l(Object[] array) {
  return array == null ? 0 : array.length;
}

static int l(byte[] array) {
  return array == null ? 0 : array.length;
}

static int l(int[] array) {
  return array == null ? 0 : array.length;
}

static int l(char[] array) {
  return array == null ? 0 : array.length;
}

static int l(Collection c) {
  return c == null ? 0 : c.size();
}

static int l(Map m) {
  return m == null ? 0 : m.size();
}

static int l(String s) {
  return s == null ? 0 : s.length();
} 


}