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

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

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

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

样例输入：

absd

abba

abdffd

样例输出：

4

2

4
一开始的代码是这样

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 char toDo[];

 int cnt[];

 int main(int argc, char const *argv[])

 {

     //freopen("input.txt","r",stdin);

     while(scanf("%s",toDo) != EOF) {

         int max = ;

         memset(cnt, , sizeof(cnt));

         cnt[] = ;

         for(int i = ; toDo[i]; i++) {

             int temp = ;

            for(int j = i-; j >= i - cnt[i-]; j--) {

                 if(toDo[j] == toDo[i]) {

                     break;

                 }

                 else {

                     temp++;

                 }

            }

            cnt[i] = temp;

            if(max < cnt[i]) {

             max = cnt[i];

            }

         }

         printf("%d\n",max);

     }

     return ;

 }

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

 #include <cstdio>

 char toDo[];

 int main(int argc, char const *argv[])

 {

     while(scanf("%s",toDo) != EOF) {

         int max = ;

         int cntl = ;

         for(int i = ; toDo[i]; i++) {

             int temp = ;

            for(int j = i-; j >= i - cntl; j--) {

                 if(toDo[j] == toDo[i]) {

                     break;

                 }

                 else {

                     temp++;

                 }

            }

            if(max < temp) {

               max = temp;

            }

            cntl = temp;

         }

         printf("%d\n",max);

     }

     return ;

 }

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

巴特西

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

最新文章

热门文章