import java.util.concurrent.TimeUnit;
import java.util.regex.Pattern;
import static java.lang.System.*;
import static java.util.concurrent.TimeUnit.NANOSECONDS;


public class Main
{
   public static void main(String[] args)
    {
        long ns = 0L;
        Pattern lazy   = Pattern.compile("^(11+?)\\1+$");
        Pattern greedy = Pattern.compile("^(11+)\\1+$" );
        ns=nanoTime();  lazy  .matcher(new Rep('1',100160079)).matches(); out.println("Lazy Rep    : "+ NANOSECONDS.toMillis(nanoTime()-ns));
        //ns=nanoTime();  greedy.matcher(new Rep('1',100160079)).matches();out.println("Greedy Rep  :"+ NANOSECONDS.toMillis(nanoTime()-ns));
        
		//ns=nanoTime(); "1".repeat( 100160079 ).matches("^(11+?)\\1+$") ; out.println("Lazy String:"+ NANOSECONDS.toMillis(nanoTime()-ns));
		//ns=nanoTime(); "1".repeat( 100160079 ).matches("^(11+)\\1+$") ; out.println("Greedy String:"+ NANOSECONDS.toMillis(nanoTime()-ns));        
		
        //no Pattern.compile()
        ns=nanoTime(); lazy.matcher("1".repeat( 100160079 )).matches(); out.println("Lazy String : "+ NANOSECONDS.toMillis(nanoTime()-ns));
        //ns=nanoTime(); greedy.matcher("1".repeat( 100160079 )).matches(); out.println("Greedy String:"+ NANOSECONDS.toMillis(nanoTime()-ns));

    }




static class Rep implements CharSequence
{
    String str = null;
    int    len;
    char  base;

    public Rep(char x, int count)
    {
        this.len  = count;
        this.base = x;
    }

    @Override
    public int length()
    {
        return len;
    }

    @Override
    public char charAt(int index)
    {
        return base;
    }

    @Override
    public CharSequence subSequence(int beginIndex, int endIndex)
    {
        if (beginIndex < 0) {
            throw new StringIndexOutOfBoundsException(beginIndex);
        }
        if (endIndex > this.len) {
            throw new StringIndexOutOfBoundsException(endIndex);
        }
        int subLen = endIndex - beginIndex;
        if (subLen < 0) {
            throw new StringIndexOutOfBoundsException(subLen);
        }
        return ((beginIndex == 0) && (endIndex == this.len)) ? this
                : new Rep(this.base, subLen);
    }

    @Override
    public String toString()
    {
        return null!=str ?  str : (this.str  = new String(new char[]{base}).repeat(len));
    }

 
}
}