先说结论，动态规划，时间复杂度最差为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;

}