在字符串中找到一个连续子字符串,没有重复并且长度最长

如题

给定一个全小写的英文字符串,请在该字符串中找到一个连续子字符串,使得子字符串没有重复的字符并且长度最长,计算此最长字符串的长度。比如:abcbdeab,最长的子字符串为cbdea,长度为5;aaaa,最长子字串为a,长度为1。

基本思想

例如:给定字符串abcabcdabc,首先从a开始,然后一直向后查找,当字符为b时,查找b是否与前面的字符相同,结果为不相同,即继续向后查找。当字符第二次为a时,判定该字符与前面的字符相同,记录子串长度,然后重新从与该字符相同的字符的后一位重新开始,即第一个字符a的后一位b开始,。直到给定字符串遍历结束,记录子字符串最大的长度。

Input:
2         //输入的第一行指定用例数量T
abcabcdabc  //输入小写字符串

bbbb

Output:

4
1

#include <stdio.h>
#include <string.h>

int find_max_len_sub_string(const char* str)
{
    int index=0,count=0;   //定义字符串下标,不重复的子串开始下标
    int len_max = 0;      //定义子串最大长度
    int len = strlen(str);    //获取字符串长度
    while(index<len)
    {
        for(int i=count; i<index; i++)    //在已经确定未重复的字符序列中查找是否有与当前字符相同的字符
        {
            if(str[i] == str[index])     //找到重复字符
            {
                index = index-count;    //当前未重复字符串的长度
                len_max = index>len_max? index:len_max;
                index = i;   //字符串下标回退
                count = i+1;   //新的子串开始下标

            }
        }
        index++; 
    }
    if(len_max == 0)  len_max=len;  //遍历结束,未找到重复字符,最大长度即为字符串长度
    return len_max;
}

int main()
{
    int t;    //指定用例数量
    scanf("%d",&t);
    while(t--)
    {
        char str[100]={};
        scanf("%s",str);
        int len = find_max_len_sub_string(str);
        printf("%d
",len);   //输出最大长度
    }
}
原文地址:https://www.cnblogs.com/xiehuan-blog/p/9017503.html