Hatena::Grouptopcoder

tsubosakaの日記

2009-04-20

SRM 439 Div1 Medium

| 20:08

言われるとなるほどと思うのだが本番ではなかなか思いつかない。

まず、$の数が1つのときは A B B B ... という周期的な列になるため容易に求まる。また$の数が2つ以上のときは変数の長さが常に2倍以上になるため、s <= 32のときのみを考えればよい。

import java.util.*;
public class EndlessStringMachine {
  int cnt(String s) {
    int cnt = 0;
    for (char c : s.toCharArray())
      if (c == '$')cnt++;
    return cnt;
  }
  char rec(String in , String p , int s , int i , List<Long> ls){
    if(s == 0)return in.charAt(i);
    long plen = ls.get(s - 1);
    for(char c : p.toCharArray())
      if(c == '$')
        if(i < plen)return rec(in, p, s - 1, i, ls);
        else i -= plen;
      else if(i-- == 0)return c;
    return '-';
  }
  public String getFragment(String in, String p, int s, int L, int R) {
    L--; R--;
    long dn = cnt(p);
    StringBuilder sb = new StringBuilder();
    if (dn == 1) {
      int plen = p.length() - 1;
      long tlen = in.length() + plen * (long)s;
      for (int i = L; i <= R; i++)
        if (i < in.length())sb.append(in.charAt(i));
        else if(i >= tlen)sb.append('-');
        else sb.append( p.charAt(1 + (i - in.length()) % plen));      
    } else {
      List<Long> ls = new ArrayList<Long>();
      ls.add((long)in.length());
      for (int i = 1; i <= s; i++) {
        long li = (ls.get(i - 1) * dn) + (p.length() - dn);
        ls.add(li);
        if (li >= R)break;
      }
      for(int index = L ; index <= R ; index++)
        sb.append(rec(in, p, ls.size() - 1 , index, ls));      
    }
    return sb.toString();
  }
}