What substring search algorithm is used by different JREs?

java.lang.String JavaDoc says nothing about the default indexOf(String开发者_运维知识库) substring search algorithm. So my question is - which substring algorithms is used by different JREs?

There's src.zip in JDK which shows implementation:

/**
 * 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;
}

fwiw (in case this Q is about the performance of different algorithms) on appropriate hardware and with a sufficiently recent oracle jvm (6u21 and later as detailed in the bug report), String.indexOf is implemented via the relevant SSE 4.2 intrinsics.. see chapter 2.3 in this intel reference doc

Here is what found for now:

Oracle JDK 1.6/1.7, OpenJDK 6/7

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;
}

IBM JDK 5.0

public int indexOf(String subString, int start) {
    if (start < 0) start = 0;
    int subCount = subString.count;
    if (subCount > 0) {
        if (subCount + start > count) return -1;
        char[] target = subString.value;
        int subOffset = subString.offset;
        char firstChar = target[subOffset];
        int end = subOffset + subCount;
        while (true) {
            int i = indexOf(firstChar, start);
            if (i == -1 || subCount + i > count) return -1; // handles subCount > count || start >= count
            int o1 = offset + i, o2 = subOffset;
            while (++o2 < end && value[++o1] == target[o2]);
            if (o2 == end) return i;
            start = i + 1;
        }
    } else return start < count ? start : count;
}

Sabre SDK

  public int indexOf(String str, int fromIndex)
  {
    if (fromIndex < 0)
      fromIndex = 0;
    int limit = count - str.count;
    for ( ; fromIndex <= limit; fromIndex++)
      if (regionMatches(fromIndex, str, 0, str.count))
        return fromIndex;
    return -1;
  }

Feel free to update this post.

As most of the time indexOf is used for small substrings in reasonable small strings it is I believe save to assume that a fairly straight forward algorithm like the one shown by Victor is used. There are more advanced algorithms that work better for large strings but AFAIK these all perform worse for relative short strings.