1. A palindrome detector
Your task for this assignment is to write a program, palindrome.c, that detects palindromes, where a palindrome is a string that consists of the same characters in the same sequence when it is reversed. For example, "amanaplanacanalpanama", "aaa", and the empty string "" are all palindromes, but "ab", "amanaplanacanalpanamb" and "abbaa" are not.
Your program should read one purported palindrome per line from stdin, and for each such line should write an output line consisting of the word PALINDROME if the input line is a palindrome, or the index of the first character that doesn't match otherwise. So, for example, on input
amanaplanacanalpanama aaa ab amanaplanacanalpanamb abbaa aaaaaabcaaaaaa
the output of your program should be
PALINDROME PALINDROME PALINDROME 0 0 1 6
2. Details
You do not need to handle lines containing the null character '\0'; however, any other character except a newline may appear in an input line.
You should not assume that the last line of input is terminated by a newline; if you read a nonempty line of input terminated by EOF, you should treat it as if it ended with a newline.
- You should not assume any limits on the size of the input lines.
Your program should free any blocks that it allocates with malloc. Your program should not produce any errors when run under valgrind with the --test=memcheck and --leak-check=yes options. (See C/valgrind for more details.)
- Your program should be self-contained: it should not call any external programs.
3. Submitting your program
Submit your program as usual with the command
/c/cs223/bin/submit 2 palindrome.c
A public test script is available in /c/cs223/Hwk2/test.palindrome.
4. Solutions
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 /* Palindrome detector.
6 *
7 * For each line of the input, prints PALINDROME if it is a palindrome
8 * or the index of the first non-matching character otherwise.
9 *
10 * Note: does not handle lines containing nulls.
11 */
12
13 /* read a line of text from stdin
14 * and return it (without terminating newline) as a freshly-malloc'd block.
15 * Caller is responsible for freeing this block.
16 * Returns 0 on error or EOF.
17 */
18 char *
19 getLine(void)
20 {
21 char *line; /* line buffer */
22 int n; /* characters read */
23 int size; /* size of line buffer */
24 int c;
25
26 size = 1;
27 line = malloc(size);
28 if(line == 0) return 0;
29
30 n = 0;
31
32 while((c = getchar()) != '\n' && c != EOF) {
33 while(n >= size - 1) {
34 size *= 2;
35 line = realloc(line, size);
36 if(line == 0) return 0;
37 }
38 line[n++] = c;
39 }
40
41 if(c == EOF && n == 0) {
42 /* got nothing */
43 free(line);
44 return 0;
45 } else {
46 line[n++] = '\0';
47 return line;
48 }
49 }
50
51 #define IS_PALINDROME (-1)
52
53 /* returns IS_PALINDROME if s is a palindrome,
54 * or index of first unmatched character otherwise. */
55 int
56 testPalindrome(const char *s)
57 {
58 int n; /* length of s */
59 int i;
60
61 n = strlen(s);
62
63 /* we only have to check up to floor(n/2) */
64 for(i = 0; i < n/2; i++) {
65 if(s[i] != s[n-1-i]) {
66 return i;
67 }
68 }
69 /* else */
70 return IS_PALINDROME;
71 }
72
73 int
74 main(int argc, char **argv)
75 {
76 char *line;
77 int mismatch;
78
79 while((line = getLine()) != 0) {
80 mismatch = testPalindrome(line);
81 if(mismatch == IS_PALINDROME) {
82 puts("PALINDROME");
83 } else {
84 printf("%d\n", mismatch);
85 }
86
87 free(line);
88 }
89
90 return 0;
91 }
92
93