1 #include <stdio.h>
2 #include <stdlib.h>
3
4 //
5 // Compare the whole thing by passing 0 as end
6 //
7 // @param str String to check for palindrome
8 // @param end For checking a substring shorter than the end of str
9 //
10 // @return int Is a palindrome (1) or not (0)
11 //
12 char is_palindrome(char* str, long len) {
13 //long len;
14 long i = 0;
15
16 // This handles comparisons of odd and even length strings
17 while(len - i > 0) {
18 if(str[i] != str[len])
19 return 0;
20
21 ++i;
22 --len;
23 }
24 return 1;
25 }
26
27
28 //
29 // Finds the largest palindrome in a data set
30 //
31 // @param data Data chunk to search for the largest palindrome
32 //
33 void find_largest_palindromes(char* data) {
34 long cursor = 0;
35 int start = 0;
36 int end = 0;
37
38 int largest = 0;
39 int largest_start = 0;
40 int largest_end = 0;
41
42 // Writing this here for sanity purposes
43 // 0 1 2 3 4 5 6
44 // r a c e c a r
45
46 // 0 1 2 3 4 5
47 // a b c c b a
48
49 while(data[cursor] != '\0') {
50 // Need to align with the center
51 // Advance end one to see if this is an even numbered palindrome
52 if(data[end + 1] != '\0') {
53 ++end;
54 }
55 // If it's not an even numbered, let's see if it's odd numbered
56 if(start > 0 && data[start] != data[end]) {
57 --start;
58 }
59 // Looks like it's not either, reset and continue
60 if(data[start] != data[end]) {
61 ++cursor;
62 start = cursor;
63 end = cursor;
64 continue;
65 }
66
67 // It seems we have found a palindrome, let's see how big...
68 while(data[start] == data[end]) {
69 if(data[end + 1] != '\0') {
70 ++end;
71 }
72 if(start > 0) {
73 --start;
74 }
75
76 }
77 if(end - start - 1 > largest) {
78 largest = end - start - 1;
79 largest_start = start + 1;
80 largest_end = end - 1;
81 }
82
83 ++cursor;
84 start = cursor;
85 end = cursor;
86 }
87 // Move start one forwards since moving it backwards resulted in a non-
88 if( largest > 1) {
89 printf("The largest palindrome is %d long\n", largest);
90 printf("It starts at %d, and ends at %d\n", largest_start, largest_end);
91 printf("%.*s\n", largest, &data[largest_start]);
92 }
93 }
94
95
96 //
97 // Function for testing one-off strings
98 // Useful for debugging
99 //
100 // @param str String to test for palindromeism
101 //
102 void palstr(char* str) {
103 if(is_palindrome(str, 0) == 1) {
104 printf("%s \e[1mis\e[0m a palindrome!\n", str);
105 } else {
106 printf("%s is \e[1mnot\e[0m a palindrome.\n", str);
107 }
108 }
109
110
111 //
112 // Ye olde' main function
113 //
114 int main(int argc, char *argv[]) {
115 if(argc < 2) {
116 printf("Please specify a string to check for palindrome-ism.\n");
117 return 1;
118 }
119
120 FILE *f = fopen(argv[1], "r");
121
122 // If the file can't be opened, try using the passed value as a palindrome
123 // test
124 if(!f) {
125 palstr(argv[1]);
126 return 0;
127 }
128
129 printf("Scanning file %s\n", argv[1]);
130
131 // Get file length
132 unsigned int flen = 0;
133 while(fgetc(f) != EOF) {
134 flen++;
135 }
136
137 rewind(f);
138
139 printf("Allocating memory\n");
140 // Allocate array for file contents
141 char* data = malloc(flen + 1);
142 unsigned int i = 0;
143 char c;
144 printf("Reading data to memory\n");
145 while((c = fgetc(f)) != EOF) {
146 data[i] = c;
147 i++;
148 }
149
150 fclose(f);
151
152 printf("Searching for palindromes\n");
153
154
155 find_largest_palindromes(data);
156 free(data);
157 return 0;
158 }
|
