如何在C++中实现返回vector的递归字符串滑动窗口切片函数

需求说明 #

要实现的功能为：接收字符串S、分片长度fragment_size、步长jump三个输入参数，按照指定的分片长度切割字符串，每次切割后按步长jump移动窗口遍历整个字符串，最终返回所有分片组成的列表。

原Python实现代码 #

import sys
# First we read the input and asign it to 3 different variables
S = sys.stdin.readline().strip()
fragment_size = sys.stdin.readline().strip()
jump = sys.stdin.readline().strip()

def window(S, fragment_size, jump):
    word = S[:fragment_size]
    if len(word)< fragment_size:
        return []
    else:
        return [word] + window(S[jump:], fragment_size, jump)

# We check that S is not an empty string and that fragment_size and jump are bigger than 0. 
if len(S) > 0 and int(fragment_size) > 0 and int(jump) > 0:
    # We print the results 
    for i in window(S, int(fragment_size), int(jump)):
        print(i)

功能示例 #

示例1 #

输入：

ACGGTAGACCT
3
1

输出：

ACG
CGG
GGT
GTA
TAG
AGA
GAC
ACC
CCT

示例2 #

输入：

ACGGTAGACCT
3
3

输出：

ACG
GTA
GAC

原错误C++代码存在的问题 #

提供的代码主要有以下几处错误：

• 定义了无用的window_list函数，返回值声明与实际逻辑不符，且使用了不需要的二维vector存储结果
• 递归逻辑错误：没有将当前分片合并到递归返回的结果列表中，每次递归的局部outp_list没有实际作用
• 返回值语法错误，终止条件处的返回写法不符合C++语法
• 缺少和Python版本对应的输入合法性校验

修正后可运行C++代码 #

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

vector<string> window(string s, int fragment_size, int jump) {
    string word = s.substr(0, fragment_size);
    // 终止条件：当前取到的分片长度不足，返回空列表
    if (word.length() < fragment_size) {
        return {};
    }
    // 递归获取后续所有分片
    vector<string> res = window(s.substr(jump), fragment_size, jump);
    // 将当前分片插入到结果列表最前面
    res.insert(res.begin(), word);
    return res;
}

int main() {
    string s;
    int fragment_size, jump;
    cin >> s;
    cin >> fragment_size;
    cin >> jump;
    // 输入合法性校验，和Python版本逻辑对齐
    if (s.size() > 0 && fragment_size > 0 && jump > 0) {
        vector<string> ans = window(s, fragment_size, jump);
        for (auto& str : ans) {
            cout << str << endl;
        }
    }
    return 0;
}

代码说明 #

• 完全对齐Python版本的递归逻辑：先取当前窗口的分片，长度不足就返回空列表，否则递归调用拿到后续所有分片，再把当前分片拼到结果的最前面返回
• 去掉了多余的辅助函数，直接在递归函数中完成结果拼接
• 增加了输入合法性校验，避免非法参数导致异常
• 测试两个示例输入均可得到对应正确输出

内容的提问来源于stack exchange，提问作者Lous