关注
先说结论,动态规划,时间复杂度最差为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;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
9720次浏览 836人参与
# 机械制造薪资爆料 #
348252次浏览 4100人参与
# 牛客帮帮团来啦!有问必答 #
1058043次浏览 16025人参与
# 通信硬件薪资爆料 #
250610次浏览 2361人参与
# 晒一晒我的offer #
3727866次浏览 57567人参与
# 面试中,你被问过哪些奇葩问题? #
19326次浏览 149人参与
# 你收到了团子的OC了吗 #
525427次浏览 6242人参与
# 毕业租房也有小确幸 #
38422次浏览 3181人参与
# 你怎么评价今年的春招? #
9588次浏览 161人参与
# 我想象的工作vs实际工作 #
104246次浏览 1682人参与
# 春招你拿到offer了吗 #
398044次浏览 5747人参与
# 提前批和秋招有什么区别 #
28908次浏览 695人参与
# 秋招开了,你想投哪些公司呢 #
132471次浏览 3426人参与
# 字节跳动工作体验 #
73441次浏览 2019人参与
# 实习生应该准时下班吗 #
88462次浏览 649人参与
# 腾讯工作体验 #
151313次浏览 1478人参与
# 来选选带哪个offer回家过年 #
191798次浏览 1838人参与
# 你的秋招进行到哪一步了 #
392971次浏览 6641人参与
# 浅聊一下我实习的辛苦费 #
99430次浏览 1002人参与
# 百度工作体验 #
28547次浏览 286人参与