Rewrote algorithm entirely

New algorithm is much more efficient. Compares small to large, rather
than large to small.

1 files changed, 42 insertions, 45 deletions

diff --git a/src/main.c b/src/main.c
index 65db782..20811a7 100644
--- a/src/main.c
+++ b/src/main.c
@@ -9,19 +9,17 @@
 //
 // @return int Is a palindrome (1) or not (0)
 //
-char is_palindrome(char* str, int len) {
+char is_palindrome(char* str, long len) {
   //long len;
-  int i = 0;
-  int n = len;
+  long i = 0;
 
   // This handles comparisons of odd and even length strings
-  while(n - i > 0) {
-    if(str[i] == str[n]) {
-      i++;
-      n--;
-    } else {
+  while(len - i > 0) {
+    if(str[i] != str[len])
       return 0;
-    }
+
+    ++i;
+    --len;
   }
   return 1;
 }
@@ -33,45 +31,43 @@ char is_palindrome(char* str, int len) {
 // @param data Data chunk to search for the largest palindrome
 //
 void find_largest_palindromes(char* data) {
-  unsigned int largest_start = 0;
-  unsigned int largest_end = 0;
-  int largest_len = 0;
-
-  // get length
-  unsigned int len = 0;
-  while(data[len] != '\0')
-    len++;
-
-  long start;
-  long end = len;
-  unsigned int palindrome;
-  while(end > 0) {
-    // Moving the start index
-    start = 0;
-    while(start < (end - largest_len)) {
-      //printf("testing s: %d  e: %d\n", start, end);
-      // Moving the end index
-
-      //printf("%.*s\n", end - start, &data[start]);
-      palindrome = is_palindrome(&data[start], end - start);
-      if(palindrome == 1) {
-        // Update the largest if this one is bigger
-        unsigned int curlen = end - start;
-        if(curlen > largest_len) {
-          largest_len = curlen;
-          largest_start = start;
-          largest_end = end;
-          printf("Found new largest: %d chars long\n", largest_len + 1);
-          break;
-        }
+  long cursor = 0;
+  int start = 0;
+  int end = 0;
+
+  int largest = 0;
+  int largest_start = 0;
+  int largest_end = 0;
+
+  // Writing this here for sanity purposes
+  // 0 1 2 3 4 5 6
+  // r a c e c a r
+
+  while(data[cursor] != '\0') {
+    while(data[start] == data[end]) {
+      if(start > 0) {
+        --start;
       }
-      start++;
+      if(data[end + 1] != '\0') {
+        ++end;
+      }
+    }
+    if(end - start - 1 > largest) {
+      largest = end - start - 1;
+      largest_start = start + 1;
+      largest_end = end - 1;
     }
-    end--;
+
+    ++cursor;
+    start = cursor;
+    end = cursor;
+  }
+  // Move start one forwards since moving it backwards resulted in a non-
+  if( largest > 1) {
+    printf("The largest palindrome is %d long\n", largest);
+    printf("It starts at %d, and ends at %d\n", largest_start, largest_end);
+    printf("%.*s\n", largest, &data[largest_start]);
   }
-  printf("Longest palindrome is %d long\n", largest_len + 1);
-  printf("It starts at %d and ends at %d\n", largest_start, largest_end);
-  printf("Value: %.*s\n", largest_end - largest_start + 1, &data[largest_start]);
 }
 
 
@@ -109,6 +105,7 @@ int main(int argc, char *argv[]) {
   }
   
   printf("Scanning file %s\n", argv[1]);
+
   // Get file length
   unsigned int flen = 0;
   while(fgetc(f) != EOF) {