fork download
copy 
  1.  
  2. #include <stdio.h>
  3.  
  4. void printSubstring(char *start, int len) {
  5.     while (len--) {
  6.         putchar(*start);
  7.         start++;
  8.     }
  9.     putchar('\n');
  10. }
  11.  
  12. char* longestUniqueSubstring(char *s, int *outLen) {
  13.     int lastSeen[256];
  14.  
  15.     for (int i = 0; i < 256; i++)
  16.         lastSeen[i] = -1;
  17.  
  18.     char *start = s;
  19.     char *end = s;
  20.  
  21.     char *bestStart = s;
  22.     int bestLen = 0;
  23.  
  24.     int index = 0;  // position in string
  25.  
  26.     while (*end != '\0') {
  27.         unsigned char c = (unsigned char)*end;
  28.  
  29.         // if character seen inside current window
  30.         if (lastSeen[c] >= start - s) {
  31.             // move start just after previous occurrence
  32.             start = s + lastSeen[c] + 1;
  33.         }
  34.  
  35.         lastSeen[c] = index;
  36.  
  37.         int len = (end - start) + 1;
  38.         if (len > bestLen) {
  39.             bestLen = len;
  40.             bestStart = start;
  41.         }
  42.  
  43.         end++;
  44.         index++;
  45.     }
  46.  
  47.     *outLen = bestLen;
  48.     return bestStart;
  49. }
  50.  
  51. int main() {
  52.     char str[] = "abcab p q r pqbcbb";
  53.  
  54.     int len = 0;
  55.     char *res = longestUniqueSubstring(str, &len);
  56.  
  57.     printf("Longest substring = ");
  58.     printSubstring(res, len);
  59.  
  60.     return 0;
  61. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Longest substring = r pqbc
https://ideone.com/DTyo3A
language:
C (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!