函数 求一个字符串中最长的没有重复的字符串。C不可使用STL模板
时间: 2024-10-16 14:15:43 浏览: 28
基于C++字符串替换函数的使用详解
5星 · 资源好评率100%
在一个字符串中找到最长没有重复字符的子串可以使用滑动窗口的思想。这里是一个简单的C语言实现示例:
```c
#include <stdio.h>
#include <stdbool.h>
// 定义一个结构体表示字符及其出现次数
typedef struct {
char ch;
int count;
} CharCount;
// 动态数组用于存储字符出现次数
CharCount* char_counts = NULL;
// 函数帮助查找最长无重复字符子串的长度
int findLengthWithNoDuplicates(char* str) {
int n = strlen(str);
if (n == 0 || char_counts == NULL) {
return 0;
}
int start = 0, max_len = 0;
bool has_seen[char_size] = {false}; // 使用布尔数组记录已见字符
for (int end = 0; end < n; end++) {
if (has_seen[str[end]]) {
// 如果遇到重复字符,则回溯到上一个唯一字符的位置
while (str[start] != str[end]) {
has_seen[char_counts[start].ch] = false;
start++;
}
start++;
} else {
// 更新最长无重复子串的起始位置和长度
has_seen[str[end]] = true;
if (end - start + 1 > max_len) {
max_len = end - start + 1;
}
}
}
return max_len;
}
int main() {
char str[] = "abcabcbb";
char_counts = (CharCount*)malloc(n * sizeof(CharCount));
printf("Longest substring without repeating characters: %d\n", findLengthWithNoDuplicates(str));
free(char_counts);
return 0;
}
```
这个程序首先创建了一个动态数组`char_counts`来跟踪每个字符出现的情况,然后从左到右遍历输入字符串。如果遇到重复字符,它会回溯到上一个唯一的字符,并更新滑动窗口的开始位置。最后返回最长无重复子串的长度。
阅读全文