ИСПОЛЬЗУЙТЕ технику скользящего окна или другую другую лучшую операцию для счетчика, определяющего тип смежных подстрок c из данной строки - PullRequest
Новая
       39

ИСПОЛЬЗУЙТЕ технику скользящего окна или другую другую лучшую операцию для счетчика, определяющего тип смежных подстрок c из данной строки

0 голосов
/ 09 апреля 2020

Я хочу, чтобы кто-нибудь помог мне, используя технику скользящего окна, чтобы решить проблему на основе подстрок.

хорошо, поэтому ПРОБЛЕМА такова: -

Вам дана строка S из n натуральных чисел (например, S = {1, 2, 3, 4, 9, 7, 2}) вы должны найти следующее: i) Подсчитать все смежные подстроки, содержащие число '2', только один раз, и эти подстроки не содержат '4' ii) Подсчитать все смежные подстроки, содержащие число '2', только один раз в каждой подстроке & ' 4 'хотя бы один раз.

Предположим, что заданная строка S = {1, 2, 3, 4, 9, 7, 2, 4}

ОБЪЯСНЕНИЕ для части (i):

все возможные смежные подстроки строки S: 

{  (1), (2), (3), (4), (9), (7), (2), (4) ,
   (1,2), (2,3), (3,4), (4,9), (9,7), (7,2), (2,4) ,
   (1,2,3), (2,3,4), (3,4,9), (4,9,7), (9,7,2), (7,2,4) ,
   (1,2,3,4), (2,3,4,9), (3,4,9,7), (4,9,7,2), (9,7,2,4) ,
   (1,2,3,4,9), (2,3,4,9,7), (3,4,9,7,2), (4,9,7,2,4) ,
   (1,2,3,4,9,7), (2,3,4,9,7,2), (3,4,9,7,2,4) ,
   (1,2,3,4,9,7,2), (2,3,4,9,7,2,4) ,
   (1,2,3,4,9,7,2,4)  }

желаемые подсчитываемые подстроки: {(2), (2), (1,2), (2,3), (7,2), (1,2,3), (9,7,2),}

, поэтому на выходе должно быть: 7

ОБЪЯСНЕНИЕ для части (ii):

все возможные смежные подстроки строки S: 

{  (1), (2), (3), (4), (9), (7), (2), (4) ,
   (1,2), (2,3), (3,4), (4,9), (9,7), (7,2), (2,4) ,
   (1,2,3), (2,3,4), (3,4,9), (4,9,7), (9,7,2), (7,2,4) ,
   (1,2,3,4), (2,3,4,9), (3,4,9,7), (4,9,7,2), (9,7,2,4) ,
   (1,2,3,4,9), (2,3,4,9,7), (3,4,9,7,2), (4,9,7,2,4) ,
   (1,2,3,4,9,7), (2,3,4,9,7,2), (3,4,9,7,2,4) ,
   (1,2,3,4,9,7,2), (2,3,4,9,7,2,4) ,
   (1,2,3,4,9,7,2,4)  }

желаемые подсчитываемые подстроки: {(2,4), (2,3,4), (7,2 , 4), (1,2,3,4), (2,3,4,9), (4,9,7,2), (9,7,2,4), (1,2,3 , 4,9), (2,3,4,9,7), (3,4,9,7,2), (4,9,7,2,4), (1,2,3,4,9,7), (3,4,9,7,2,4),}

, поэтому на выходе должно быть: 13

Можем ли мы как-то выполнить эти две подзадачи в O (N) или даже лучше сложность времени? Если да, то как написать код для этого? Если кто-нибудь поможет мне с этим, я буду очень благодарен.

...