`
zhu_jinlong
  • 浏览: 5052 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

最长不重复子串

 
阅读更多
问题:

找到一个字符串中的一个连续子串,这个子串内不能有任何两个字符是相同的,并且这个子串是符合要求的最长的。



程序:
代码
/************************************************************************/
/* 求最长不重复子串                                                     */
/************************************************************************/

void lnorepstr(char*  s)
{
    char A[26];
    int  i, j;
    int  maxi, maxlen = 0;
    int  len = strlen(s);

//    for(i = 0; i < 26; i++)
//        A[i] = -1;

    memset(A, -1, 26);
    for (i = 0; i < len; i++)
    {
        A[s[i] - 'a'] = 1;
        for(j = i+1 ; j < len; j++)
        {
            if(A[s[j]-'a'] == -1) //该字符没有出现
            {
                A[s[j]-'a'] = 1;
                if(j - i> maxlen)
                {
                    maxlen = j - i;
                    maxi = i;
                }
            }
            else
                break;
        }
        memset(A, -1, 26);
    }
    printf("longest no repeat string: %.*s\n", maxlen+1, &s[maxi]);
}



假设字符串全部是由小写字母组成,则内层循环最多执行26次,即最长不重复子串的长度为26,此时,时间复杂度为O(26n)。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics