Program opened below. You can scroll through the algorithm, Java code and output.
Program 13
Extend a String to a Palindrome
Question
Read a word and append the minimum possible characters to its end so that the resulting string becomes a palindrome.
Algorithm
Step 1: Start and input a word.
Step 2: Set the starting position of the possible palindromic suffix to zero.
Step 3: Define a function to check whether a suffix is a palindrome.
Step 4: Place one pointer at the suffix start.
Step 5: Place another pointer at the end of the string.
Step 6: Compare the characters under the two pointers.
Step 7: Return false if they differ.
Step 8: Otherwise move the pointers towards each other.
Step 9: Return true when the pointers meet or cross.
Step 10: Test the suffix beginning at the current starting position.
Step 11: If it is not palindromic, advance the starting position.
Step 12: Repeat until the longest palindromic suffix is found.
Step 13: Copy the original word into the answer.
Step 14: Append the earlier prefix in reverse order.
Step 15: Display the completed palindrome and stop.
Java program
Javaimport java.util.*;
class AppendPalindrome {
static boolean palindrome(String s, int start) {
int left = start;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int start = 0;
while (!palindrome(s, start)) {
start++;
}
String result = s;
for (int i = start - 1; i >= 0; i--) {
result += s.charAt(i);
}
System.out.println(result);
}
}Sample output
Input: ABCA
Output: ABCACBA