Какой алгоритм поиска подстроки используется различными JRE?

Question

java.lang.String JavaDoc ничего не говорит об алгоритме поиска подстроки по умолчанию indexOf(String). Итак, мой вопрос - какие алгоритмы подстроки используются различными JRE?

Answer 1

Вот что сейчас найдено:

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

Не стесняйтесь обновлять этот пост.

Answer 2

fwiw (в случае, если этот Q о производительности разных алгоритмов) на соответствующем оборудовании и с достаточно новым oracle jvm (6u21 и более поздними, как описано в отчете об ошибке ), реализовано String.indexOfчерез соответствующие встроенные функции SSE 4.2 .. см. главу 2.3 в этом справочном документе по Intel

Answer 3

В JDK есть src.zip, который показывает реализацию:

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

Answer 4

Поскольку большую часть времени indexOf используется для небольших подстрок в разумных небольших строках, я полагаю, стоит предположить, что используется довольно прямой алгоритм, подобный показанному Виктором.Существуют более продвинутые алгоритмы, которые работают лучше для больших строк, но AFAIK все они работают хуже для относительных коротких строк.