Warning: session_start(): open(/var/lib/php/sessions/sess_0g4i3foej3s8hh0nimhjakc4p2, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51
Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
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 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();
}
}