Member 13772639 Ответов: 2

Как объяснить эту очередь с помощью алгоритма

1. Suppose you are given a source string S [0 ..n − 1] of length n, consisting of symbols a and b. Suppose further that you are given a pattern string P [0 ..m − 1] of length m « n, consisting of symbols a, b, and *, representing a pattern to be found in string S. The symbol * is a “wild card” symbol, which matches a single symbol, either a or b. The other symbols must match exactly. The problem is to output a sorted list M of valid “match positions”, which are positions j in S such that pattern P matches the substring S[j..j + |P |− 1]. For example, if S = ababbab and P = ab *, then the output M should be [0, 2]. Describe a straightforward, na¨ıve algorithm to solve the problem. Your algorithm should run in time O (nm).

Что я уже пробовал:

Я много пытался, но всегда путаюсь, чтобы объяснить этот вопрос.

2 Ответов

Рейтинг:
15

OriginalGriff

Мы не делаем вашу домашнюю работу - и тренируемся как делать что-то-это часть вашей задачи.

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

Оттуда вы можете начать реализовывать его в коде.

Рейтинг:
0

KarstenK

Ваша домашняя работа с 3-мя различными персонажами не слишком сложна. Вы должны только искать и сравнивать в некоторых строках. Это приятнострунный учебник покажу вам необходимые операции.
Полезным может быть и такое заявление о переключении

string s = "ab*";
switch( s[i] )
{
  case 'a':
   //needed operation
   break;
} 
//or compare
if(s[i] == 'a') {
}