题目1530:最长不重复子串
时间限制:1 秒
内存限制:128 兆
特殊判题:否
提交:362
解决:106
- 题目描述:
-
最长不重复子串就是从一个字符串中找到一个连续子串,该子串中任何两个字符都不能相同,且该子串的长度是最大的。
- 输入:
-
输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串,字符串的长度不大于10000。
- 输出:
-
对于每组测试用例,输出最大长度的不重复子串长度。
- 样例输入:
-
absd abba abdffd
- 样例输出:
-
4 2 4
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; const int maxn = 10010; char str[maxn]; bool vis[30];//hash inline int ind(char x) { return x - 'a'; } void work() { int maxv = 0; int i, j, cnt = 0; int len = strlen(str); memset(vis, false, sizeof(vis)); for(i = 0; i < len; i++) { memset(vis, false, sizeof(vis)); cnt = 0; for(j = i; j < len; j++) { //开始没有回溯,wa char t = str[j]; if(!vis[ind(t)]) { vis[ind(t)] = true; cnt++; if(maxv < cnt) maxv = cnt; }else break; } } printf("%d ", maxv); } int main() { memset(str, ' ', sizeof(str)); while(scanf("%s", str) != EOF) { getchar(); work(); memset(str, ' ', sizeof(str)); } return 0; }