Thursday, September 22, 2011

To find the longest substring with unique characters in a given string


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

typedef struct {

    const char *start;
    size_t len;

}Substring;


Substring longestSubstring(const char *s){

    Substring ret = {s, 1};
    
    Substring cur = {s, 1};
        
    size_t i, len = strlen(s);
    
    const char *p = NULL;
    
    for(i = 1; i < len; ++i){
    
            p = memchr(cur.start, s[i], cur.len);
            
            if(p){
            
                    if(cur.len > ret.len)
                            ret = cur;
                                
                    cur.len -= (p - cur.start) + 1;
                    
                    cur.start = p + 1;
            }
            
            cur.len++;
    
    }

    if(cur.len > ret.len)
            ret = cur;
    

    return ret;
}


int main(){

    char s[64];
    
    scanf("%s", s);

    Substring sub = longestSubstring(s);
    
    ((char *)sub.start)[sub.len] = '\0';

    printf("%s\n", sub.start);

    return 0;

}

0 comments:

Post a Comment