题解 | #在字符串中找出连续最长的数字串#动态规划

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

int main() {
    string str;
    while (cin >> str) {
        // 动态规划（参考最长回文子串）
        int len = str.size();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        int maxLen = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                bool a = std::isdigit(str[i]);
                bool b = std::isdigit(str[j]);
                int curLen = j - i + 1;
                // 如果i，j对应的长度小于二，且都是数字，直接置为true
                if (a && b && curLen <= 2) {
                    dp[i][j] = true;
                } else if (a && b) {
                    // 继承之前的状态
                    dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j])
                    maxLen = std::max(maxLen, curLen);
            }
        }
        // 找到所有maxLen的子串
        vector<string> res;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int curLen = j - i + 1;
                if (dp[i][j] && curLen == maxLen) {
                    res.push_back(str.substr(i, curLen));
                }
            }
        }
        // 输出
        for (int i = 0; i < res.size(); i++) {
            cout << res[i];
        }
        cout << "," << maxLen << endl;
    }
}
// 64 位输出请用 printf("%lld")