Поиск подстроки в Java

Я пытаюсь создать алгоритм, который найдет индекс заданной подстроки (которую я пометил pattern) в данном String (который я пометил text). Этот метод можно сравнить с String.indexOf(String str). Помимо общих отзывов, мне любопытно, какова временная сложность моего метода, и я был бы признателен, если бы кто-нибудь помог мне в этом разобраться.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

public class SubstringSearch {
    public static void main(String[] args) {
        String text = "This is a test String";
        String pattern = "is a";
        int index = search(pattern, text);
        System.out.println(index);
    }

    private static int search(String pattern, String text) {
        int patternLength = pattern.length();
        int textLength = text.length();

        Set<Integer> set = new HashSet<>(textLength);
        List<Integer> addList = new ArrayList<>(textLength);

        for (int i = 0; i < textLength; i++) {
            set.add(0);

            for (Integer index : set) {
                if (pattern.charAt(index) == text.charAt(i)) {
                    addList.add(index + 1);
                }
            }

            set.clear();
            set.addAll(addList);

            if (set.contains(patternLength)) {
                return i - patternLength + 1;
            }
        }

        throw new NoSuchElementException();
    }
}

Хорошая реализация, мои предложения:

• Ошибка: text="aa aaa" и pattern="aaa" возвращает 1 вместо 3. Следует ли обрабатывать этот пограничный случай, зависит от вашего варианта использования, но если text может быть любой строкой, тогда ее следует учитывать.
• Проверка ввода: если pattern является пустым или нулевым, возникает исключение нулевого указателя. Вы можете исправить это, добавив условие в начале метода.
• Именование: имя метода search слишком общий. Рассмотрим более конкретный вариант, например firstIndexOf или похожие. Имена переменных set и addList также можно улучшить.
• Порядок аргументов: это личное мнение, но я бы поставил ищущую строку (text) перед строкой для поиска (pattern).
• Исключение, если не найдено: для такой функции обычно возвращается -1 вместо исключения, когда pattern не найден. В случае сомнения, задокументируйте метод.
• Тестирование: этот метод заслуживает более одного теста, возможно, с использованием JUnit.
• Сложность: сложность кажется $ O (textLenght * patternLength) $. Внешний цикл for повторяется на text, а внутренний цикл for не будет делать больше, чем patternLength итерации в противном случае pattern.charAt(index) вызовет исключение. Временная сложность String#indexOf является $ O (п * м) $ поэтому основное отличие вашего решения в отношении сложности (наихудший случай), вероятно, заключается в сложности пространства. В любом случае, лучше сначала сосредоточиться на правильной функциональности, а потом на производительности.

В качестве справки это собственная реализация:

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