一尘不染

C ++:如何将字符串拆分为大小均匀的较小字符串?

algorithm

在C ++中,如何将字符串拆分为大小均匀的较小字符串?

例如,我有一个字符串“ 012345678”,并希望将其拆分为5个较小的字符串,这应该返回类似“ 01”,“ 23”,“ 45”,“ 67”,“8”的内容。

我在确定较小字符串的长度时遇到了麻烦。在前面的示例中,原始字符串的大小为9,我想将其拆分为5个较小的字符串,因此除最后一个字符串外,每个较小的字符串的长度应为9/5
= 1,但最后一个字符串的长度应为9- 1 * 4 = 5,这是不可接受的。

因此 ,此问题正式定义是 :将原始字符串拆分为n个子字符串,并且两个子字符串的长度之差不得超过1。

我的重点不是C ++语法或库。这是设计算法的方法,以使返回的字符串的大小几乎相等。


阅读 264

收藏
2020-07-28

共1个答案

一尘不染

要将N个项目划分为M个部分(长度在1个单位之内),可以将公式(N*i+N)/M-(N*i)/M用作i第n个部分的长度,如下所示。

 #include <string>
 #include <iostream>
 using namespace std;

 int main() {
   string text = "abcdefghijklmnopqrstuvwxyz";
   int N = text.length();
   for (int M=3; M<14; ++M) {
     cout <<" length:"<< N <<"  parts:"<< M << "\n";
     int at, pre=0, i;
     for (pre = i = 0; i < M; ++i) {
       at = (N+N*i)/M;
       cout << "part " << i << "\t" << pre << "\t" << at;
       cout << "\t" << text.substr(pre, at-pre) << "\n";
       pre = at;
     }
   }
   return 0;
 }

例如,当M为4或5时,上面的代码将产生:

  length:26  parts:4
 part 0 0   6   abcdef
 part 1 6   13  ghijklm
 part 2 13  19  nopqrs
 part 3 19  26  tuvwxyz
  length:26  parts:5
 part 0 0   5   abcde
 part 1 5   10  fghij
 part 2 10  15  klmno
 part 3 15  20  pqrst
 part 4 20  26  uvwxyz
2020-07-28