java indexOf function complexity is O(n*m) where n is length of the text and m is a length of pattern
here is indexOf original code

   /**
     * Returns the index within this string of the first occurrence of the
     * specified substring. The integer returned is the smallest value
     * <i>k</i> such that:
     * <blockquote><pre>
     * this.startsWith(str, <i>k</i>)
     * </pre></blockquote>
     * is <code>true</code>.
     *
     * @param   str   any string.
     * @return  if the string argument occurs as a substring within this
     *          object, then the index of the first character of the first
     *          such substring is returned; if it does not occur as a
     *          substring, <code>-1</code> is returned.
     */
    public int indexOf(String str) {
    return indexOf(str, 0);
    }

    /**
     * Returns the index within this string of the first occurrence of the
     * specified substring, starting at the specified index.  The integer
     * returned is the smallest value <tt>k</tt> for which:
     * <blockquote><pre>
     *     k &gt;= Math.min(fromIndex, this.length()) && this.startsWith(str, k)
     * </pre></blockquote>
     * If no such value of <i>k</i> exists, then -1 is returned.
     *
     * @param   str         the substring for which to search.
     * @param   fromIndex   the index from which to start the search.
     * @return  the index within this string of the first occurrence of the
     *          specified substring, starting at the specified index.
     */
    public int indexOf(String str, int fromIndex) {
        return indexOf(value, offset, count,
                       str.value, str.offset, str.count, fromIndex);
    }

    /**
     * Code shared by String and StringBuffer to do searches. The
     * source is the character array being searched, and the target
     * is the string being searched for.
     *
     * @param   source       the characters being searched.
     * @param   sourceOffset offset of the source string.
     * @param   sourceCount  count of the source string.
     * @param   target       the characters being searched for.
     * @param   targetOffset offset of the target string.
     * @param   targetCount  count of the target string.
     * @param   fromIndex    the index to begin searching from.
     */
    static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
    if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
    }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
    if (targetCount == 0) {
        return fromIndex;
    }

        char first  = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j] ==
                         target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

you can simply implements the KMP algorithm without using of indexOf Like this

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;


public class Main{
    int failure[];
    int i,j;
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out=new PrintWriter(System.out);
    String pat="",str="";
    public Main(){
            try{

            int patLength=Integer.parseInt(in.readLine());
            pat=in.readLine();
            str=in.readLine();
            fillFailure(pat,patLength);
            match(str,pat,str.length(),patLength);
            out.println();
            failure=null;}catch(Exception e){}

        out.flush();
    }
    public void fillFailure(String pat,int patLen){
        failure=new int[patLen];
        failure[0]=-1;
        for(i=1;i<patLen;i++){
            j=failure[i-1];
            while(j>=0&&pat.charAt(j+1)!=pat.charAt(i))
                j=failure[j];
            if(pat.charAt(j+1)==pat.charAt(i))
                failure[i]=j+1;
            else
                failure[i]=-1;
        }
    }
    public void match(String str,String pat,int strLen,int patLen){
        i=0;
        j=0;
        while(i<strLen){
            if(str.charAt(i)==pat.charAt(j)){
                i++;
                j++;
                if(j==patLen){
                    out.println(i-j);
                    j=failure[j-1]+1;
                }
            } else if (j==0){
                    i++;
            }else{
                j=failure[j-1]+1;
            }

        }
    }
    public static void main(String[] args) {
        new Main();
    }
}

I guess we are talking about appending single characters. Appending a string of length N would have an O(N).

Answer: Because with increasing length, copying becomes less frequent by the same factor by which it becomes more expensive.

Let's assume the capacity doubles when full. Doesn't matter, could be a factor of 1.1, 3, or whatever, but it's easier to talk about.

Doubling 1 needs to copy 1000 chars, which on average over these first 1000 means 1 char to copy per char appended.

Doubling 2 needs to copy 2000 chars, which on average over the past 1000 after the first copy means 2 chars to copy per char appended.

Doubling 3 needs to copy 4000 chars, which on average over the past 2000 means 2 chars to copy per char appended.

Doubling 4 needs to copy 8000 chars, which on average over the past 4000 means 2 chars to copy per char appended.

&c.

So before the first doubling, it's free, then you pay half the price, and the the price settles at 2 chars per char appended on average.

In java, if the call is string1.indexOf(string2) the time cost would be O(m - n) where m is the length of string1 and n is the length of string2.

In my opinion it should be constant(O(1)) time complexity.

This is not possible. Since Java strings are immutable, while StringBuilders are mutable, all operations that produce a String must make a copy.

If this is true, how can I get a substring within a constant time complexity?

You cannot. Without a copy, changing characters inside a substring would mutate the String, which is not allowed.

1. Inserting at index 0 has a time complexity of O(n). So if you already have 500 characters in the internal array, it needs to shift those 500 chars over just to make space for the new char at the first index. So no, it is not.

2. Yes, it works.

Do what OffbeatDrizzle suggests, or simply create a function that will iterate over the StringBuilder in reverse and print out the contents- assuming this is what is required. If you need an object then reversing it at the end is the best way.

If the StringBuilder needs to increase its capacity, that involves copying the entire character array to a new array. You can avoid this by initially setting the capacity so it won't have to do this. (This should be easy since you know the length of the int array and the maximum number of characters in the String representation of an int.)

If you avoid the need to increase the capacity, the complexity would seem to just be O(n). When you append, you're just copying the character array from the String to the end of the character array in the StringBuilder.

(Yes, it depends on the implementation, but it would be a rather poor implementation of StringBuilder if it couldn't append in O(n) time.)