Самый быстрый алгоритм поиска строки

Я изобрел самый быстрый алгоритм поиска строки. Может кто-нибудь доказать, что он не самый быстрый?

Я не рассматриваю худшие сценарии.

Алгоритм можно найти здесь: https://sourceforge.net/projects/fastest-string-search-algo/files/

    /*
     * Choudhary algorithm
     */
    public static int choudharyStringSearchAlgorithm(char[] text, char[] pattern) {

        int i = 0;
        int index = 0;
        int end_index = 0;
        boolean not_found = false;

        int text_len = text.length;
        int pattern_len = pattern.length;

        int pi_44 = pattern_len - 1;
        int pi_34 = (3 * pattern_len) / 4;
        int pi_24 = pattern_len / 2;
        int pi_14 = pattern_len / 4;

        int[] skip_table = new int[ASIZE];

        // preprocess pattern and fill skip_table
        for (i = 0; i < pattern_len; i++) {
            skip_table[pattern[i]] = pattern_len - 1 - i;
        }

        // now search
        for (i = 0; i < text_len; i++) {

            if ((text_len - i) < pattern_len) {
                return -1;
            }

            if (pattern[pi_44] != text[i + pi_44]) {
                if (skip_table[(int) (text[i + pi_44])] > 0) {
                    i = i + skip_table[(int) (text[i + pi_44])] - 1;
                }
                continue;
            }

            if (pattern[0] != text[i]) {
                continue;
            }

            if (pattern[pi_24] != text[i + pi_24]) {
                continue;
            }

            if (pattern[pi_34] != text[i + pi_34]) {
                continue;
            }

            if (pattern[pi_14] != text[i + pi_14]) {
                continue;
            }

            end_index = i + pi_44;
            not_found = false;

            for (index = i; index <= end_index; index++) {
                if (text[index] != pattern[index - i]) {
                    not_found = true;
                    break;
                }
            } // end of inner for loop

            if (not_found == false) { // match is found
                return i;
            }

        } // end of outer for loop

        return -1;

    } // end of choudharyStringSearchAlgorithm

Если вы ищете длинные шаблоны, ваш алгоритм в большинстве случаев выигрывает (предпочтение отдается длинным строкам до конца текста, насколько это возможно), но если вы сравните алгоритмы с шаблонами длиной до 100 символов (поиск людей), Бойер-Мур курит всех и даже не близко.

Изменить: после некоторого тестирования я обнаружил, что ваш алгоритм хуже на длинных шаблонах, чем если бы вы только что реализовали таблицу пропуска.

Изменить 2: На самом деле вот реализация, которая последовательно работает быстрее, чем любой другой алгоритм в вашей коллекции, более чем в 95% случаев:

public class MyTextSearch implements TextSearch
{
    @Override
    public int search(
            char[] text,
            char[] pattern
    )
    {
        int[] skip_table = new int[256];
        int patternLength = pattern.length - 1;
        char lastPatternChar = pattern[patternLength];

        Arrays.fill(skip_table, patternLength);

        for (int i = 0; i < pattern.length; i++)
        {
            skip_table[pattern[i]] = patternLength - i - 1;
        }

        for (int i = 0; i < text.length; i++)
        {
            if (i + patternLength >= text.length)
            {
                return -1;
            }

            char lastTextChar = text[i + patternLength];
            if (lastPatternChar != lastTextChar)
            {
                i += skip_table[lastTextChar];
                continue;
            }

            if (isEqual(text, i, pattern))
            {
                return i;
            }
        }

        return -1;
    }

    private boolean isEqual(
            char[] text,
            int at,
            char[] pattern
    )
    {
        for (int j = 0; j < pattern.length; j++)
        {
            if (text[at + j] != pattern[j])
            {
                return false;
            }
        }

        return true;
    }

    @Override
    public String name()
    {
        return "My Text Search";
    }
}

Я немного отредактировал ваш код, и он включен https://github.com/blazmrak/fastest-string-search если ты заинтересован.