如何在给定的字符串中找到一串字母序列？

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++;
    }
}

我尝试过这个方法，但对我没用。并且我不明白是否存在其他方法来找到它。请帮帮我。

- Jubair Uddin

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;

- mahbubcseju

---

通常情况下，当您访问数组的一个元素时，您需要确保该元素实际上存在。如果msg实际上为空，则char ch = msg[0];是越界的。 - Tiger Yu

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

演示

- NutCracker

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的代码对空消息无效。

- Benquan Yu

---

这是最简单的方法！ - Tiger Yu

Answer 4

使用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;
    }
}

{{链接1：演示}}

- Jarod42

Answer 5

欢迎来到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;
}

为了帮助解决算法问题和编写代码，我建议以下几个步骤：

首先，用多种方式写出你的问题，包括它所需的输入和你想要的输出。

其次，在纸上尝试解决它，思考逻辑 - 一个好的提示是尝试理解你自己如何解决它。你的大脑是一个很好的问题解决者，如果你能听取它的建议，你就可以将其转化为代码（虽然不总是最有效率）。

第三，用纸笔计算，手动按照你的步骤跟随来检查你的解决方案是否符合预期。然后，你就可以将解决方案转化为代码，明确知道你需要写什么。

- mukunda