Как найти последовательность букв в заданной строке?

Question

Моя строка "AAABBAABABB", и я хочу получить результат как

A = 3
B = 2
A = 2
B = 1 
A = 1
B = 2

Я пытался использовать

for (int i = 0; i < n - 1; i++) {
    if (msg[i] == msg[i + 1]) {
        if(msg[i]==A)
            a++;
        else
            b++;
    }
}

Я пробовал это, но это не сработало для меня. И я не понимаю, есть ли другие способы узнать это. Пожалуйста, помогите мне.

Answer 1

Перебрать массив следующим образом:

1. Если i = 0, мы можем установить переменную как 0-й символ и счетчик на 1.

2. Если i-й символ равен предыдущему символу, мы можем увеличить счетчик.

3. Если i-й символ не равен (i-1) -ому символу, мы можем напечатать символ, счетчик и начать отсчет новый символ.

Попробуйте следующий фрагмент:

char ch = msg[0];
int cnt = 1;

for (int i = 1; i < n; i ++){
   if(msg[i] != msg[i-1]){
      cout<<ch<<" "<<cnt<<endl;
      cnt = 1;
      ch = msg[i];
   }
   else {
      cnt++;
   }
}

cout<<ch<<" "<<cnt<<endl;

Answer 2

Вы можете использовать std::vector<std::pair<char, std::size_t>> для хранения вхождений символов.

В конечном итоге у вас будет что-то вроде:

#include <iostream>
#include <utility>
#include <vector>
#include <string>

int main() {
    std::vector<std::pair<char, std::size_t>> occurrences;
    std::string str{ "AAABBAABABB" };

    for (auto const c : str) {
        if (!occurrences.empty() && occurrences.back().first == c) {
            occurrences.back().second++;
        } else {
            occurrences.emplace_back(c, 1);
        }
    }

    for (auto const& it : occurrences) {
        std::cout << it.first << " " << it.second << std::endl;
    }

    return 0;
}

Будет выведено:

A 3
B 2
A 2
B 1
A 1
B 2

Демо

Answer 3

Это очень похоже на кодирование длин серий. Я думаю, что самый простой способ (меньше строк кодов), о котором я могу думать, выглядит следующим образом:

void runLength(const char* msg) {
    const char *p = msg;
    while (p && *p) {
        const char *start = p++;  // start of a run
        while (*p == *start) p++;  // move p to next run (different run)
        std::cout << *start << " = " << (p - start) << std::endl;
    }
}

Обратите внимание, что:

1. Эта функция не должна знать длину перед вводом строки, он остановится в конце строки, '\ 0'.
2. Он также работает с пустой строкой и NULL. Оба они работают: runLength(""); runLength(nullptr); Я пока не могу комментировать, если вы посмотрите внимательно, код mahbubcseju не работает для пустого сообщения.

Answer 4

Добро пожаловать в stackoverflow. Ооо, проблема с алгоритмом? Я добавлю рекурсивный пример:

#include <iostream>

void countingThing( const std::string &input, size_t index = 1, size_t count = 1 ) {
   if( input.size() == 0 ) return;

   if( input[index] != input[index - 1] ) {
      std::cout << input[index - 1] << " = " << count << std::endl;
      count = 0;
   }

   if( index < input.size() ) return countingThing( input, index + 1, count + 1 );
}

int main() {
   countingThing( "AAABBAABABB" );
   return 0;
}

Чтобы помочь отработать алгоритмы и выяснить, что писать в вашем коде, я предлагаю несколько шагов:

Во-первых, опишите вашу проблему разными способами, какой тип ввода он ожидает и каким вы хотите, чтобы результат был.

Во-вторых, попробуйте решить это на бумаге, как будет работать logi c - хороший совет попытайтесь понять, как ВЫ решите эту проблему. Ваш мозг хорошо решает проблемы, и если вы можете прислушиваться к тому, что он делает, вы можете превратить его в код (хотя он не всегда самый эффективный).

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

Answer 5

С std вы можете сделать:

void print_sequence(const std::string& s)
{
    auto it = s.begin();    
    while (it != s.end()) {
        auto next = std::adjacent_find(it, s.end(), std::not_equal_to<>{});
        next = next == s.end() ? s.end() : next + 1;

        std::cout << *it << " = " << std::distance(it, next) << std::endl;
        it = next;
    }
}

Demo