Количество подстрок данной строки, содержащей определенный символ

Question

Какой может быть самый эффективный алгоритм для подсчета количества подстрок данной строки, содержащих данный символ.

например. для abb b

подстроки: a, b, b, ab, bb, abb. Ответ: строки связываются как минимум один раз = 5.

PS. я решил этот вопрос, сгенерировав все подстроки и проверив O (n ^ 2). Просто хочу знать, может ли быть лучшее решение для этого.

Answer 1

Пусть вам нужно найти подстроки с символом X.

Сканирование строки слева направо, сохраняя позицию последнего X: lastX с начальным значением -1

Когда вы встретите X в позиции i, добавьте i+1 к результату и обновите lastX
(это количество подстрок, оканчивающихся на текущую позицию, и все они содержат X)

Когда вы встречаете другого персонажа, добавьте lastX + 1 к результату
(это опять число подстрок, оканчивающихся на текущую позицию и содержащих X),
потому что самый правый возможный старт подстроки - это позиция последнего X

Алгоритм является линейным.
Пример:

a X a a X a
            good substrings                            overall     
idx  char   ending at idx             lastX   count    count
 0    a      -                        -1       0        0  
 1    X     aX X                       1       2        2 
 2    a     aXa Xa                     1       2        4
 3    a     aXaa Xaa                   1       2        6 
 4    X     aXaaX XaaX aaX aX X        4       5        11 
 5    a     aXaaXa XaaXa aaXa aXa Xa   4       5        16 

Код Python:

def subcnt(s, c):
    last = -1
    cnt = 0
    for i in range(len(s)):
        if s[i] == c:
            last = i
        cnt += last + 1
    return cnt

print(subcnt('abcdba', 'b'))

Answer 2

Думайте о подстроке как о выборе двух элементов из промежутков между буквами в вашей строке и включении всего между ними (где есть пробелы на крайних концах строки).

Для строки длиныn, есть выбор (n + 1,2) подстрок.

Из них для каждого набора из k символов, которые не включают цель, есть выбор (k + 1,2) подстрок, которые тольковключить буквы из этой подстроки.Все остальные подстроки основной строки должны включать цель.

Ответ: выберите (n + 1,2) - сумма (выберите (k_i + 1,2)), где k_i - длины серийбуквы, которые не включают цель.

Answer 3

Вы можете перевернуть это и отсканировать вашу строку на наличие вхождений вашего письма.Каждый раз, когда вы находите вхождение в некоторой позиции i, вы знаете, что оно содержится по определению во всех подстроках, которые его содержат (т.е. во всех подстроках, которые начинаются до или в i и заканчиваются в или после i),поэтому вам нужно только хранить пары индексов для определения подстрок вместо явного хранения подстрок.

При этом вам все равно понадобится O (n²) при таком подходе, потому что, хотя вы и не используетеНе забывайте повторять подстроки, как показывает ваш пример, вы не хотите считать одну и ту же подстроку дважды, поэтому вам все равно нужно убедиться, что вы не выбрали одну и ту же пару индексов дважды.

Answer 4

Давайте рассмотрим строку как abcdaefgabb и данный символ как a.

• Зацикливание строки char по char.
• Если символ соответствует заданному символу, скажем a по индексу 4, то есть количество подстрок, которые будут содержать a от abcda до aefgabb.Итак, мы добавляем (4-0 + 1) + (10 - 4) = 11.Они представляют собой подстроки как abcda, bcda, cda, da, a, ae, aef, aefg, aefga, aefgab и aefgabb.
• Это относится к везде, где вы найдете a, как вы найдете его по индексу 0, а также по индексу 8.
• Окончательный ответ - сумма вышеупомянутых математических операций.

Обновление: Вам нужно будет поддерживать 2 указателя между последним a и текущим a, чтобы избежать вычисления дублирующих подстрок, которые начинаются с конца и заканчиваются тем же индексом.