字符串格式的时间优化：通过在单词之间添加空格将行填充到长度为K.

Question

我编写了使用空格键符号将字符串扩展为长度K的代码。我的代码有效，但对于冗长的字符串来说还不够快。我尝试优化代码是不够的，所以任何帮助将不胜感激。

例：

Input:
16
i love apples
Output:
i   love  apples

目标是在1秒内进行任何字符串处理，如果K = BUFSIZE。

这是代码：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define BUFSIZE 1000005

int main(void) {
    char s = ' ';
    char str[BUFSIZE], res[BUFSIZE] = "";
    int K;
    scanf("%d\n", &K);
    fgets(str, BUFSIZE, stdin);
    int i, j = 0, len = strlen(str) - 1, maxP = 0, p = 0, c = 0, sum = 0;
    if (K == len) {
        printf("%s", str);
        return 0;
    }
    for (i = 0; i < len; i++) {
        if (str[i] == s) {
            p++;
            sum++;
        }
        else if (str[i] != s && i - 1 >= 0 && str[i - 1] == s) {
            if (p > maxP) {
                maxP = p;
                p = 0;
            }
            else {
                p = 0;
            }
            c++;
        }
    }
    i = 0;
    K -= len;
    do {
        if (str[i] == s) {
            res[j] = s;
            p++;
            j++;
            i++;
        }
        else if (str[i] != s && i - 1 >= 0 && str[i - 1] == s) {
            if (sum / c == maxP && K > 0) {
                res[j] = s;
                K--;
                j++;
            }
            if (p < maxP && K > 0) {
                sum++;
                res[j] = s;
                K--;
                j++;
                p = 0;
            }
            res[j] = str[i];
            i++;
            j++;
        }
        else {
            res[j] = str[i];
            i++;
            j++;
        }
        if (i == len) {
            i = 0;
            j = 0;
            strcpy(str, res);
            len = strlen(str);
            strcpy(res, "");
        }
    } while (K > 0);
    if (i < len) {
        while (i < len) {
            res[j] = str[i];
            i++;
            j++;
        }
    }
    printf("%s", res);
    return 0;
}

Answer 1

在这种情况下，大多数线性算法应该足够快。性能可能受I / O的限制。

这是一个简单的O（n）算法，用空格填充行到宽度：

1. 查找/([ ]*[^ ]*)*/正则表达式描述的输入行中的单词数：

   size_t count_words(const char* str)
   {
     size_t count = 0;
     for ( ; ; ) { // ([ ]*[^ ]*)*
       for ( ; *str && *str == ' '; ++str) ; // skip separator
   
       if (!*str)
         break;
   
       ++count; // found word
   
       for ( ; *str && *str != ' '; ++str) ; // skip word chars
   
     }
     return count;
   }

2. 找到所需的行数，知道所需的行宽和输入中的单词（非空格）字符数：

   size_t count_nonspaces(const char* str)
   {
     size_t count = 0;
     for ( ; *str; ++str)
       if (*str != ' ')
         ++count;
     return count;
   }

3. 它允许在单词之间找到所需的空格数。如果空格不能在单词之间均匀分布，则必要时通过调整单词之间的空格从左到右插入余数
4. 主循环将单词从源复制到目标，插入计算出的单词之间的空格数：

   int main(void)
   {
     const size_t max_width = 1000005;
     assert (max_width <= (SIZE_MAX - 2));
   
     // read desired width, line
     size_t width, len;
     char *line;
     if (!(line = malloc(max_width + 2)) // '\n' + '\0'
         || !fgets(line, max_width + 2, stdin) // read 1st line
         || sscanf(line, "%zu", &width) != 1
         || width > max_width
         || !fgets(line, max_width + 2, stdin) // read 2nd line
         || !(len = strlen(line)) // last char is always '\n'
         || line[len-1] != '\n') {
       exit(EXIT_FAILURE); //NOTE: let OS free memory hereafter
     }
   
     if (len > width) {     // input line is wide enough
       fputs(line, stdout); // output as is
       exit(EXIT_SUCCESS);
     }
   
   
     // pad *line* to *width* with spaces, normalize space
     line[--len] = '\0'; // chop newline
     const size_t word_count = count_words(line);
     // total number of spaces
     const size_t m = width - count_nonspaces(line);
     // number of spaces between words
     const size_t space_count = word_count > 1 ? m / (word_count - 1) : m;
     // the rest of spaces
     size_t rest = word_count > 1 ? m % (word_count - 1) : 0;
   
     // insert spaces between words
     char *str = line, *dest = malloc(width + 1);
     if (!dest) exit(EXIT_FAILURE);
     char *start = dest, *end = dest + width;
     for ( ; ; ) { // ([ ]*[^ ]*)*
       for ( ; *str == ' '; ++str) ; // skip separator
   
       // copy found word
       for ( ; *str && *str != ' '; ++str)
         *dest++ = *str;
   
       if (dest == end) {
         *dest = '\0';
         break;
       }
   
       // append spaces
       size_t nspaces = space_count;
       if (rest) { // distribute the rest of spaces: one for each word from
         // left to right
         --rest;
         ++nspaces;
       }
       memset(dest, ' ', nspaces);
       dest += nspaces;
     }
     puts(start);
   }

Example：

$ cc *.c && ./a.out <<<$'16\n i love apples'
i   love  apples

Answer 2

我在Android手机上运行所以我不在这里发布代码，但我会给你一些提示。

首先，您不需要逐个插入空格。您可以创建一个字符串数组，将句子分成一个单词数组并存储它们。

现在你有了多少个单词。您可以使用一个非常简单的整数除法来确定每个“单词分隔”应该有多少个空格，以及从左到右添加多少剩余空格。

你已经完成了所有这些。您现在可以连接单词并在连接期间添加空格。整个过程可以在O（N）的时间内完成，其中N是原始字符串的长度。