首页 > 代码库 > 找出字符串中最长不重复的子串
找出字符串中最长不重复的子串
这题 是群里一个人发出来的 我就试着去做了下 他们说 这题蛮水的 我擦了-.-
花了很长时间 在原有的代码上 修改了很多 自己测了很多组数据 觉得应该对了
我的方法应该是 hash的思想 但这边我是直接用了map去存 也没差
假如有个字符串是abbcda 那么我们应该在遍历到第二个b的时候 计算出此时的 len 并且将在b之前的字符 重置为 未访问
我的思想就是这样的 - 觉得 看代码可以读懂.
1 #include <iostream> 2 #include <cstring> 3 #include <map> 4 using namespace std; 5 6 map<char,int>mp; 7 int main() 8 { 9 int x , y , st , end , ans , sum , len , mmin , temp;10 char str[110];11 while( cin >> (str+1) )12 {13 mmin = st = end = ans = 1;14 len = strlen(str+1);15 mp.clear();16 for( int i = 1 ; i<=len ; i++ )17 {18 if( !mp[ str[i] ] )19 {20 mp[ str[i] ] = i;21 if( i==len )22 {23 sum = i+1-st;24 if( ans<sum )25 {26 ans = sum;27 x = st;28 y = i+1;29 }30 }31 }32 else33 {34 sum = i - st;35 temp = mp[ str[i] ];36 for( int j = mmin ; j<=mp[ str[i] ] ; j++ )37 {38 mp[ str[j] ] = 0;39 }40 mmin = temp + 1;41 mp[ str[i] ] = i;42 if( ans<sum )43 {44 ans = sum;45 x = st;46 y = i ;47 }48 st = temp + 1;49 }50 } 51 cout << x << " " << y << endl;52 cout << ans << endl;53 }54 return 0;55 }
每天 群里会有很多有意思的问题 我会尽量将我会的问题 贴出来.
如果 代码有错误 请告诉我 谢谢
找出字符串中最长不重复的子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。