题意

找字符串中最大长度的所有数字串，输出它们和最大长度

限制：字符串长度不大于200

方法

遍历

对字符串进行一次遍历，同时记录字符串起始位置，和最大长度。

以样例数据abcd12345ed125ss123058789为例

每当我们遇到非数字时把数字起始坐标设为当前坐标+1

而每次是数字时，进行最大值更新判断，和记录最大值对应的坐标

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[210];
    while(~scanf("%s",&s)){
        int n = strlen(s);// 字符串长度
        int p = 0; // 当前数字开始
        int m = 0; // 最大长度 
        vector<pair<int,int> > stend; // 记录最长的开始结束节点
        for(int i = 0;i<n;i++){
            if(isdigit(s[i])){
                if( i-p+1 > m ){ // 更大
                    m = i-p+1; // 更新最大长度
                    stend = {}; // 清空
                }
                if( i-p+1 == m){
                    stend.push_back({p,i}); // 记录
                }
            }else{
                p = i + 1;
            }
        }
        for(auto [st,e]:stend){
            for(int i = st;i<=e;i++){
                printf("%c",s[i]); // 输出数字
            }
        }
        printf(",%d\n",m); // 输出长度
    }
    return 0;
}

复杂度分析

时间复杂度: 每个位置访问和操作代价都是常数级别，所以时间复杂度为$O(n)O(n)$

空间复杂度: 主要存储字符串消耗，为$O(n)O(n)$

长度从大到小

既然是最长的，那么如果按长度从大到小搜索，一旦找到一个满足，则就是要求的结果

所以采取：先遍历长度,再遍历起始坐标,最后检验合法性 来实现

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[210];
    while(~scanf("%s",&s)){
        int n = strlen(s);// 字符串长度
        int p = 0; // 当前数字开始
        int m = 0; // 最大长度 
        for(int l = n;l > 0;l--){ // 遍历长度
            bool found = false;
            for(int i = 0 ; i+l-1<n; i++){ // 遍历起始坐标
                bool alldigit = true;
                for(int j = 0;j<l;j++){ // 检查合法性
                    if(!isdigit(s[i+j]))alldigit = false;
                }
                if(alldigit){ // 合法
                    found = true;
                    for(int j = 0;j<l;j++){ // 输出
                        printf("%c",s[i+j]);
                    }
                }
            }
            if(found){
                printf(",%d\n",l); // 长度
                break;
            }
        }
    }
    return 0;
}

复杂度分析

时间复杂度: 因为是循环套循环，最坏情况全都不是连续数字，所以时间复杂度为$O(n^3)O(n^3)$

空间复杂度: 主要是字符串存储消耗，所以空间复杂度为$O(n)O(n)$