Skip to content

Instantly share code, notes, and snippets.

@uwi

uwi/TSUBSTR.java Secret

Created Dec 13, 2013
Embed
What would you like to do?
TSUBSTR(TLE). 書きなおしたほうがいいかなと思っているけどTLEが取れる気がしない。
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class TSUBSTR2 {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
// long S = System.nanoTime();
int n = ni(), Q = ni();
char[] s = ns(n);
int[] from = new int[n-1];
int[] to = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] g = packU(n, from, to);
SuffixAutomaton sa = SuffixAutomaton.build(s, g, 0);
sa.sortTopologically();
long[] ds = sa.preprocessDistinctSubstring();
out.println(ds[0]);
SuffixAutomaton.Node[][] fmap = sa.makeFixedMap();
for(int i = 0;i < Q;i++){
char[] alp = ns(26);
long K = nl();
out.println(sa.kthDistinctSubstring(K, ds, alp, fmap));
}
}
public static class SuffixAutomaton {
public Node t0;
public int len;
public Node[] nodes;
public int gen;
public Node[][] makeFixedMap()
{
Node[][] map = new Node[gen][26];
for(int i = 0;i < gen;i++){
for(int j = 0;j < nodes[i].np;j++){
map[i][nodes[i].next[j].key-'a'] = nodes[i].next[j];
}
}
return map;
}
private SuffixAutomaton(int n)
{
gen = 0;
nodes = new Node[2*n];
this.t0 = makeNode(0, false);
}
private Node makeNode(int len, boolean isCloned)
{
Node node = new Node();
node.id = gen;
node.isCloned = isCloned;
node.len = len;
nodes[gen++] = node;
return node;
}
public static class Node
{
public int id;
public int len;
public char key;
public Node link;
private Node[] next = new Node[3];
public boolean isCloned;
public int np = 0;
public int hit = 0;
public void putNext(char c, Node to)
{
to.key = c;
if(hit<<31-(c-'a')<0){
for(int i = 0;i < np;i++){
if(next[i].key == c){
next[i] = to;
return;
}
}
}
hit |= 1<<c-'a';
if(np == next.length){
next = Arrays.copyOf(next, np*2);
}
next[np++] = to;
}
public boolean containsKeyNext(char c)
{
return hit<<31-(c-'a')<0;
// for(int i = 0;i < np;i++){
// if(next[i].key == c)return true;
// }
// return false;
}
public Node getNext(char c)
{
if(hit<<31-(c-'a')<0){
for(int i = 0;i < np;i++){
if(next[i].key == c)return next[i];
}
}
return null;
}
}
public static SuffixAutomaton build(char[] labels, int[][] g, int root)
{
int n = labels.length;
SuffixAutomaton sa = new SuffixAutomaton(n);
sa.len = n;
int[] stack = new int[n+1];
int[] inds = new int[n+1];
Node[] lasts = new Node[n+1];
stack[0] = root;
lasts[0] = sa.extend(sa.t0, labels[root]);
int sp = 1;
while(sp > 0){
int cur = stack[sp-1], ind = inds[sp-1];
Node last = lasts[sp-1];
if(ind == g[cur].length){
sp--;
}else{
stack[sp] = g[cur][inds[sp-1]++];
if(sp-2 >= 0 && stack[sp] == stack[sp-2])continue;
inds[sp] = 0;
lasts[sp] = sa.extend(last, labels[stack[sp]]);
sp++;
}
}
return sa;
}
public static SuffixAutomaton build(char[] str)
{
int n = str.length;
SuffixAutomaton sa = new SuffixAutomaton(n);
sa.len = str.length;
Node last = sa.t0;
for(char c : str){
last = sa.extend(last, c);
}
return sa;
}
public Node extend(Node last, char c)
{
if(last.containsKeyNext(c)){
return last.getNext(c);
}
Node cur = makeNode(last.len+1, false);
Node p;
for(p = last; p != null && !p.containsKeyNext(c);p = p.link){
p.putNext(c, cur);
}
if(p == null){
cur.link = t0;
}else{
Node q = p.getNext(c); // not null
if(p.len + 1 == q.len){
cur.link = q;
}else{
// Node clone = new Node(p.len+1, true); // TODO understand
Node clone = makeNode(p.len+1, true);
clone.next = Arrays.copyOf(q.next, q.next.length);
clone.hit = q.hit;
clone.np = q.np;
clone.link = q.link;
for(;p != null && q.equals(p.getNext(c)); p = p.link){ // TODO understand
p.putNext(c, clone);
}
q.link = cur.link = clone;
}
}
return cur;
}
public void lexSort()
{
for(int i = 0;i < gen;i++){
Node node = nodes[i];
Arrays.sort(node.next, 0, node.np, new Comparator<Node>() {
public int compare(Node a, Node b) {
return a.key - b.key;
}
});
}
}
public void sortTopologically()
{
int[] indeg = new int[gen];
for(int i = 0;i < gen;i++){
for(int j = 0;j < nodes[i].np;j++){
indeg[nodes[i].next[j].id]++;
}
}
Node[] sorted = new Node[gen];
sorted[0] = t0;
int p = 1;
for(int i = 0;i < gen;i++){
Node cur = sorted[i];
for(int j = 0;j < cur.np;j++){
if(--indeg[cur.next[j].id] == 0){
sorted[p++] = cur.next[j];
}
}
}
for(int i = 0;i < gen;i++)sorted[i].id = i;
nodes = sorted;
}
public String toString()
{
StringBuilder sb = new StringBuilder();
for(Node n : nodes){
if(n != null){
sb.append(String.format("{id:%d, len:%d, link:%d, cloned:%b, ",
n.id,
n.len,
n.link != null ? n.link.id : null,
n.isCloned));
sb.append("next:{");
for(int i = 0;i < n.np;i++){
sb.append(n.next[i].key + ":" + n.next[i].id + ",");
}
sb.append("}");
sb.append("}");
sb.append("\n");
}
}
return sb.toString();
}
public String toGraphviz(boolean next, boolean suffixLink)
{
StringBuilder sb = new StringBuilder("http://chart.apis.google.com/chart?cht=gv:dot&chl=");
sb.append("digraph{");
for(Node n : nodes){
if(n != null){
if(suffixLink && n.link != null){
sb.append(n.id)
.append("->")
.append(n.link.id)
.append("[style=dashed],");
}
if(next && n.next != null){
for(int i = 0;i < n.np;i++){
sb.append(n.id)
.append("->")
.append(n.next[i].id)
.append("[label=")
.append(n.next[i].key)
.append("],");
}
}
}
}
sb.append("}");
return sb.toString();
}
public String label(Node n)
{
if(n.isCloned){
return n.id + "C";
}else{
return n.id + "";
}
}
public String toDot(boolean next, boolean suffixLink)
{
StringBuilder sb = new StringBuilder("digraph{\n");
sb.append("graph[rankdir=LR];\n");
sb.append("node[shape=circle];\n");
for(Node n : nodes){
if(n != null){
if(suffixLink && n.link != null){
sb.append("\"" + label(n) + "\"")
.append("->")
.append("\"" + label(n.link) + "\"")
.append("[style=dashed];\n");
}
if(next && n.next != null){
for(int i = 0;i < n.np;i++){
sb.append("\"" + label(n) + "\"")
.append("->")
.append("\"" + label(n.next[i]) + "\"")
.append("[label=\"")
.append(n.next[i].key)
.append("\"];\n");
}
}
}
}
sb.append("}\n");
return sb.toString();
}
public int lcslen(char[] t)
{
if(t.length == 0)return 0;
Node v = t0;
int l = 0, best = 0;
for(int i = 0;i < t.length;i++){
while(v != t0 && !v.containsKeyNext(t[i])){
v = v.link;
l = v.len;
}
if(v.containsKeyNext(t[i])){
v = v.getNext(t[i]);
l++;
}
if(l > best){
best = l;
}
}
return best;
}
public long[] preprocessDistinctSubstring()
{
int n = gen;
// preprocess
long[] dp = new long[n];
for(int i = n-1;i >= 0;i--){
dp[i] = 1;
Node node = nodes[i];
for(int j = 0;j < node.np;j++){
int toid = node.next[j].id;
dp[i] += dp[toid];
}
}
return dp;
}
public long numberOfDistinctSubstrings(){
long[] dp = new long[gen];
dp[0] = 1;
long ret = 0;
for(int i = 0;i < gen;i++){
Node n = this.nodes[i];
ret += dp[i];
for(int j = 0;j < n.np;j++){
dp[n.next[j].id] += dp[i];
}
}
return ret-1; // remove empty
}
public String kthDistinctSubstring(long K, long[] dp, char[] alp, Node[][] fmap)
{
if(K <= 0)return null;
if(K > dp[0])return "-1";
K--;
// greedy
Node cur = t0;
StringBuilder sb = new StringBuilder();
while(K > 0){
K--;
//// f[cur.np]++;
for(int j = 0;j < 26;j++){
if(cur.hit<<31-(alp[j]-'a')<0){
Node next = fmap[cur.id][alp[j]-'a'];
int toid = next.id;
if(K-dp[toid] < 0){
sb.append(next.key);
cur = next;
break;
}else{
K -= dp[toid];
}
}
}
}
return sb.toString();
}
}
// static int[] f = new int[27];
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for(int f : from)
p[f]++;
for(int t : to)
p[t]++;
for(int i = 0;i < n;i++)
g[i] = new int[p[i]];
for(int i = 0;i < from.length;i++){
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment