九度oj 题目1530：最长不重复子串

题目描述：: 最长不重复子串就是从一个字符串中找到一个连续子串，该子串中任何两个字符都不能相同，且该子串的长度是最大的。

输入：: 输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于10000。

输出：: 对于每组测试用例，输出最大长度的不重复子串长度。

样例输入：

absd
abba
abdffd

样例输出：

4
2
4
一开始的代码是这样

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4  
 5 char toDo[10002];
 6 int cnt[10002];
 7  
 8 int main(int argc, char const *argv[])
 9 {
10     //freopen("input.txt","r",stdin);
11     while(scanf("%s",toDo) != EOF) {
12         int max = 0;
13         memset(cnt, 0, sizeof(cnt));
14         cnt[0] = 1;
15         for(int i = 1; toDo[i]; i++) {
16             int temp = 1;
17            for(int j = i-1; j >= i - cnt[i-1]; j--) {
18                 if(toDo[j] == toDo[i]) {
19                     break;
20                 }
21                 else {
22                     temp++;
23                 }
24            }
25            cnt[i] = temp;
26            if(max < cnt[i]) {
27             max = cnt[i];
28            }
29         }
30         printf("%d
",max);
31     }   
32     return 0;
33 }

后来发现不需要cnt[]，只需记住上一个cnt即可，代码如下

 1 #include <cstdio>
 2 char toDo[10002];
 3 int main(int argc, char const *argv[])
 4 {
 5     while(scanf("%s",toDo) != EOF) {
 6         int max = 0;
 7         int cntl = 1;
 8         for(int i = 1; toDo[i]; i++) {
 9             int temp = 1;
10            for(int j = i-1; j >= i - cntl; j--) {
11                 if(toDo[j] == toDo[i]) {
12                     break;
13                 }
14                 else {
15                     temp++;
16                 }
17            }
18            if(max < temp) {
19               max = temp;
20            }
21            cntl = temp;
22         }
23         printf("%d
",max);
24     }   
25     return 0;
26 }

考虑用尺取法解此题会不会更快一些?