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