Подсчитать уникальное появление подстроки в списке слов, не зная подстроки?

* Я пытаюсь подсчитать уникальные появления подстроки внутри списка слов * Поэтому проверьте список слов и определите, есть ли в каких-либо словах подстроки, основанные на минимальных символах, которые встречаются несколько раз, и подсчитайте их . Я не знаю никаких подстрок.

Это рабочее решение, где вы знаете подстроку, но что, если вы не знаете? Существует минимальное количество символов, на котором основаны слова.

Найдет все слова, в которых «Книга» является подстрокой слова. С помощью функции php ниже.

Требуемый результат instad:

book count (5)
stor count (2)

person Rubytastic    schedule 21.06.2012    source источник
comment
Это не работа для preg_match. Взгляните на Суффиксное дерево / массив.   -  person nhahtdh    schedule 21.06.2012
comment
вы пытаетесь найти вхождения подстроки, которую вы получаете, например файл, то есть он известен во время выполнения, но не во время записи программы. ИЛИ найти все повторяющиеся подстроки в строке. Или что-то другое.   -  person ctrl-alt-delor    schedule 21.06.2012
comment
Итак, вы ищете самую длинную общую уникальную подстроку? Это довольно сложная задача и тема научных исследований. Хотел бы я найти хорошие ссылки ...   -  person deceze♦    schedule 21.06.2012
comment
@deceze да, я хочу найти на основе MINIMUM_CHAR количество уникальных подстрок, которые встречаются в загруженном списке слов.   -  person Rubytastic    schedule 21.06.2012
comment
@richard Я пытаюсь найти уникальную общую подстроку (основанную на минимальном символе) в тексте, не зная подстроки.   -  person Rubytastic    schedule 21.06.2012
comment
Если вы ищете самую длинную общую подстроку, вам нужно выполнить рекурсию. Похоже, что вычислительная сложность составляет O (pow (2)) или O (pow (3)), если это возможно, сделать в разумные, но, возможно, длительные сроки.   -  person ctrl-alt-delor    schedule 21.06.2012
comment
в чем именно проблема?: Вы разместили код - он ведет себя не так, как вы хотите?   -  person kontur    schedule 21.06.2012
comment
@kontur код представляет собой пример, как описано в тексте, что код работает, но с знанием слова для поиска другими словами.   -  person Rubytastic    schedule 21.06.2012
comment
@richard, не могли бы вы объяснить это поподробнее? возможно, с небольшим отрывком. Я имею в виду, как в коде будет выглядеть это уравнение? Я не вижу этого за пределами концепции   -  person Rubytastic    schedule 21.06.2012
comment
Примечание хранилище не является подстрокой хранилища (в примере добавлено к вопросу)   -  person ctrl-alt-delor    schedule 21.06.2012


Ответы (2)


Это мое первое приближение: незаконченный, непроверенный, имеет как минимум 1 ошибку и написан на eiffel. Что ж, я не собираюсь делать за тебя всю работу.

deferred class
    SUBSTRING_COUNT
feature
    threshold : INTEGER_32 =5

    biggest_starting_substring_length(a,b:STRING):INTEGER_32
        deferred
    end

    biggest_starting_substring(a,b:STRING):STRING
    do
        Result := a.substring(0,biggest_starting_substring_length(a,b))
    end

    make_list_of_substrings(a,b:STRING)
    local
        index:INTEGER_32
        this_one: STRING
    do
        from
            a_index := b_index + 1
        invariant
            a_index >=0 and a_index <= a.count
        until
            a_index >= a.count
        loop
            this_one := biggest_starting_substring(a.substring (a_index, a.count-1),b)
            if this_one.count > threshold then
                list.extend (this_one)
            end
        variant
            a.count - a_index
        end
    end -- biggest_substring

    list : ARRAYED_LIST[STRING]

end
person ctrl-alt-delor    schedule 21.06.2012
comment
спасибо Ричард, я взглянул на это, я не стремился получить функциональный фрагмент от кого-то, чтобы просто обсудить, возможно ли это сделать. Никогда раньше не слышал об Эйфеле. Необходимо проверить, доступны ли вообще те функции, которые вы используете, для php. - person Rubytastic; 21.06.2012
comment
Я не использую много функций, только {STRING} .substring (он принимает строку и два числа, первый индекс и последний индекс нужной подстроки), {LIST} .extend (добавляет элемент в конец списка), { STRING} .count) он сообщает вам, какова длина строки) - person ctrl-alt-delor; 21.06.2012

person    schedule
comment
Спасибо, теперь я вижу, что это единственный подход, который возможен достойным образом, а не сложным. Не могли бы вы, возможно, предоставить простую функцию или какой-нибудь код, демонстрирующий это? Я понимаю концепцию, но не совсем понимаю код - person Rubytastic; 21.06.2012
comment
Вам не нужно беспокоиться о длине в шаблоне поиска, тогда вы можете отбросить максимальную длину, и это будет быстрее по длине порядка. - person ctrl-alt-delor; 21.06.2012
comment
См. Мою правку с примером кода PHP. Интересная проблема :) - person kontur; 23.06.2012