!747

m {
  static class Ref {
    int line, chars;
    
    *() {}
    *(int *line, int *chars) {}
  }
  
  static class Line {
    Ref left; // take chars from beginning of existing line
    S middle;
    Ref right;// take chars from end of existing line
    
    S text() {
      ret leftToString(left) + middle + rightToString(right);
    }
    
    int getCompression() {
      int l = length();
      ret l == 0 ? 100 : (int) (100-l(middle)*100L/l);
    }
    
    int length() {
      ret refLen(left) + l(middle) + refLen(right);
    }
    
    int originalLine(int myIdx) {
      ret left != null && left.chars == length() ? left.line : myIdx;
    }  
  }
  
  static new L<Line> lines;

  p {
    readLocally("lines");
    makeAndroid3("Input Storer Bot.");
    print("Lines: " + l(lines) + ". Unpacked size: " + toK(totalSize()) + "K. Compression: " + totalCompression() + "%");
  }
  
  static synchronized S answer(S s) {
    new Matches m;
    
    if (match3("add *", s, m)) {
      S line = m.unq(0);
      add(line);
      int compression = last(lines).getCompression();
      ret "OK. Compression: " + compression + "%. Lines: " + l(lines);
    }
    
    if (match3("get *", s, m)) {
      int i = parseInt(m.unq(0));
      ret quote(lines.get(i).text());
    }
    
    if (match3("get total compression", s)) {
      ret totalCompression() + "%";
    }
    
    ret standardQuery(s, "lines");
  }
  
  // index of line that the line is a copy of
  static int originalLine(int i) {
    ret lines.get(i).originalLine(i);
  }

  static S leftToString(Ref ref) {
    ret ref == null ? "" : lines.get(ref.line).text().substring(0, ref.chars);
  }
  
  static S rightToString(Ref ref) {
    ret ref == null ? "" : rsubstring(lines.get(ref.line).text(), ref.chars);
  }
  
  static int refLen(Ref ref) {
    ret ref == null ? 0 : ref.chars;
  }
  
  static synchronized void add(S s) {
    S _s = s;
    new Line l;
    l.left = findPrefix(s);
    //print("left: " + structure(l.left));
    if (l.left != null)
      s = s.substring(l.left.chars);
    l.right = findSuffix(s);
    //print("right: " + structure(l.left));
    if (l.right != null)
      s = s.substring(0, s.length()-l.right.chars);
    l.middle = s;
    lines.add(l);
    assertEquals(l.text(), _s); // sanity check!
    saveLocally("lines");
  }
  
  // unoptimized
  static Ref findPrefix(S s) {
    if (s.isEmpty()) ret null;
    Ref best = null;
    for (int i = l(lines)-1; i >= 0; i--) {
      Line l = lines.get(i);
      int n = commonPrefix(l.text(), s).length();
      if (n > 0 && (best == null || n > best.chars)) {
        best = new Ref(originalLine(i), n);
        if (n == s.length()) ret best; // optimum, quit
      }
    }
    ret best;
  }
  
  // unoptimized
  static Ref findSuffix(S s) {
    if (s.isEmpty()) ret null;
    Ref best = null;
    for (int i = l(lines)-1; i >= 0; i--) {
      Line l = lines.get(i);
      int n = commonSuffix(l.text(), s).length();
      if (n > 0 && (best == null || n > best.chars)) {
        best = new Ref(originalLine(i), n);
        if (n == s.length()) ret best; // optimum, quit
      }
    }
    ret best;
  }
  
  static long totalSize() {
    long len = 0;
    for (Line l : lines)
      len += l.length();
    ret len;
  }
  
  static int totalCompression() {
    long middle = 0, len = 0;
    for (Line l : lines) {
      middle += l(l.middle);
      len += l.length();
    }
    ret len == 0 ? 100 : (int) (100-middle*100/len);
  }
}