找出字符串中最长不重复的子串

这题是群里一个人发出来的我就试着去做了下他们说这题蛮水的我擦了-.-

花了很长时间在原有的代码上修改了很多自己测了很多组数据觉得应该对了

我的方法应该是 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             else
33             {
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 }

View Code

每天群里会有很多有意思的问题我会尽量将我会的问题贴出来.

如果代码有错误请告诉我谢谢

just follow your heart