先说结论，动态规划，时间复杂度最差为O(n3)。 递推公式为dp[i][j] = str[ dp[i][j-1] +j-i+1 ] == str[j]?dp[i][j-1]:dp[dp[i][j-1]] 递推公式优点难懂，举个例子： abcab 设数组dp[len][len]，其中dp[i][j]表示 上一个str[i,j]的开始位置 初始化:因为str[0,0] = a,之前没出现过，dp[0][0] = -1 同理str[1,1] = -1,dp[2][2] = -1, 因为str[3,3] = a,上一次出现的位置为0，因此dp[3][3] = 0 因为str[4,4] = b,上一次出现的位置为1，因此dp[4][4] = 1. #include <iostream> #include <vector> #include <map> using namespace std; void getAllSub(const string str){     const int len = str.length();     map<char,int> mymap;     vector<vector<int>> myvec(len,vector<int>(len,-1));     for(int i =0;i<len;i++){         if(mymap.count(str[i]) == 0){             mymap[str[i]] = i;         }else{             myvec[i][i] = mymap[str[i]];             mymap[str[i]] = i;         }     }     for(int i =0;i<len;i++)         for(int j =i;j<len;j++){             if(i == j){                 if(myvec[i][j] != -1 && myvec[myvec[i][j]][myvec[i][j]] == -1)                     cout<<str.substr(i,1)<<endl;                 continue;             }             int tmp = myvec[i][j-1];             while(tmp != -1){                 if(str[j] == str[tmp+j-i]){                     myvec[i][j] = tmp;                     if(myvec[tmp][tmp+j-i-1] == -1) cout<<str.substr(i,j-i+1)<<endl;                     break;                 }else tmp = myvec[tmp][tmp+j-i-1];             }         } } int main() {     getAllSub("ababa");     return 0; }