LeetCode - Longest Substring Without Repeating Characters（最长不重复子串）

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 int isRepeat(char *a, int left, int right);
  5 int getRight(char *s, int left, int right);
  6 int getLeft(char *s, int left, int right);
  7 int getNonRepeat(char *s, int left, int right);
  8 int lengthOfLongestSubstring(char* s);
  9 
 10 int main(void) {
 11 
 12   char a[100];
 13   gets(a);
 14   fprintf(stderr, "you input a string: [%s]\n", a);
 15   fprintf(stderr, "不重复子串的长度为%d\n", lengthOfLongestSubstring(a));
 16 }
 17 
 18 
 19 int getRight(char *s, int left, int right) {
 20 
 21   int map[127], i;
 22   memset(map, 0, sizeof(map));
 23 
 24   int l = (left + right)/2;
 25   int r = l+1;
 26 
 27   if(s[l] == s[r]) {
 28     return 0;
 29   }
 30 
 31   int pos = s[l]%127;
 32   map[pos] = map[pos] + 1;
 33   pos = s[r]%127;
 34   map[pos] = map[pos] + 1;
 35   int count = 2;
 36   for(i=r+1; i<=right && s[i] != '\0'; i++) {
 37     pos = s[i]%127;
 38     if ( (map[pos] = map[pos] + 1) > 1)
 39       break;
 40     else
 41       count++;
 42   }
 43 
 44   for(i=l-1; i>=left; --i) {
 45     pos = s[i]%127;
 46     if ( (map[pos] = map[pos] + 1) > 1)
 47       return count;
 48     else
 49       count++;
 50   }
 51 
 52   return count;
 53 }
 54 
 55 int getLeft(char *s, int left, int right) {
 56 
 57   int map[127], i;
 58   memset(map, 0, sizeof(map));
 59 
 60   int l = (left + right)/2;
 61   int r = l+1;
 62   if(s[l] == s[r]) {
 63     return 0;
 64   }
 65   int pos = s[l]%127;
 66   map[pos] = map[pos] + 1;
 67   pos = s[r]%127;
 68   map[pos] = map[pos] + 1;
 69   int count = 2;
 70 
 71   for(i=l-1; i>=left; --i) {
 72     pos = s[i]%127;
 73     if ( (map[pos] = map[pos] + 1) > 1)
 74       break;
 75     else
 76       count++;
 77   }
 78 
 79   for(i=r+1; i<=right && s[i] != '\0'; i++) {
 80     pos = s[i]%127;
 81     if ( (map[pos] = map[pos] + 1) > 1)
 82       return count++;
 83     else
 84       count++;
 85   }
 86 
 87   return count;
 88 }
 89 
 90 int isRepeat(char *a, int left, int right) {
 91   int map[127] ,i;
 92   memset(map, 0, sizeof(map));  /* clear map */
 93   for(i=left; i<=right && a[i] != '\0'; i++) {
 94     int pos = a[i]%127;
 95     if((map[pos] = map[pos] + 1) > 1)
 96       return map[pos];
 97   }
 98   return 0;
 99 }
100 
101 int getNonRepeat(char *s, int left, int right) {
102 
103 
104 
105   if(isRepeat(s, left, right) == 0) { /* 如果这个串本身就是自己的最大不重复子串 */
106     printf("%d   %d\n", left, right);
107     return right-left + 1;
108   }
109 
110   int len = right - left + 1;
111   if(len == 0)
112     return 0;
113   else if(len == 1)
114     return 1;
115   else if(len == 2 && s[left] == s[right])
116     return 1;
117   else {
118     int n_l = getRight(s, left, right);
119     int n_r = getLeft(s, left, right);
120     int sub_n_l = getNonRepeat(s, left, (left+right)/2);
121     int sub_n_r = getNonRepeat(s, (left+right)/2+1, right);
122 
123     if(n_l < n_r)
124       n_l = n_r;
125     if(n_l < sub_n_l)
126       n_l = sub_n_l;
127     if(n_l < sub_n_r)
128       n_l = sub_n_r;
129 
130     return n_l;
131   }
132 }
133 
134 int lengthOfLongestSubstring(char* s) {
135   int length = 0, i=0;
136   while(s[i++] != '\0')
137     length++;
138   printf("输入的字符串的长度为%d\n", length);
139   return getNonRepeat(s, 0, length-1);
140 }