用C++写出给定一个字符串s,请找出其中不含有重复字符的最长长串的长度,每行一个字符串,最后一个字符串未尾加上“,”作为结束标志,按照顺序输出每行一个最长子串的长度。运用滑动窗口法,并进行分析。
时间: 2024-03-01 08:23:08 浏览: 85
分析:
滑动窗口法是一种解决字符串/数组子串或子序列问题的有效方法,可以在O(n)的时间复杂度内解决这类问题。
具体思路是,维护一个滑动窗口,每次向右移动一格,如果当前字符不在窗口内,则将其加入窗口中;如果当前字符已经在窗口内,则将窗口左端点移动到重复字符的下一位。在移动的过程中,记录窗口的最大长度即可。
代码实现如下:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 1005
int main()
{
char s[MAXN];
int vis[256], len, ans;
while (scanf("%s", s) != EOF) {
memset(vis, 0, sizeof(vis)); // 初始化
len = strlen(s);
int i = 0, j = 0;
ans = 0;
while (j < len) {
if (!vis[s[j]]) { // 当前字符不在窗口内
vis[s[j]] = 1;
ans = ans > j - i + 1 ? ans : j - i + 1;
j++;
} else { // 当前字符已经在窗口内
vis[s[i]] = 0;
i++;
}
}
printf("%d\n", ans);
}
printf(",");
return 0;
}
```
注意,这里使用了一个vis数组来记录当前字符是否在窗口内,同时将数组初始化为0。在每次移动窗口时,如果当前字符已经在窗口内,则将窗口左端点i右移一位,并将vis[s[i]]设为0,表示将该字符从窗口中移除。如果当前字符不在窗口内,则将其加入窗口中,并记录窗口的最大长度。
另外,由于题目要求每行一个最长子串的长度,因此在每次处理完一个字符串后需要输出ans的值。最后一个字符串后面需要输出一个逗号作为结束标志。
阅读全文