Palindrome
By Vinícius Fernandes dos Santos, Centro Federal de Educação Tecnológica de Minas Gerais 
Brazil
By Vinícius Fernandes dos Santos, Centro Federal de Educação Tecnológica de Minas Gerais Brazil
A palindrome is a string such that its reversal is equal to the original string. In other words, it is a string that, when read backwards, is equal to the original string. For example BANANAB is a palindrome, while BANANAS not. In this problem we are interested in an issue a little more interesting.
Given a string S, we want to find a subsequence that is a palindrome. A subsequence is a string that can be obtained from the removal of zero or more characters of the original string. For example ANNA is a subsequence of BANANAS.
It will also be given a set of S positions is called special positions. Its task is to find the size of the substring that is a palindrome and contains the largest number of possible special positions. If more than a subsequence maximizing the number of special positions, you must print the size of the largest.
The input consists of two lines. The first line contains a string of capital letters S with at least 1 and a maximum of 2000 characters. The second line contains an integer N (0 ≤ N ≤ |S|), indicating the number of special positions we are interested in include the palindrome, followed by N distinct numbers from 1 to |S|, even containing the positions special S.
Your program must print a single integer representing the size of the largest palindrome possible, as defined above.
| Input Samples | Output Samples |
|
BANANAS 0 |
5 |
|
BANANAS 1 7 |
1 |
|
ACDAAACX 3 2 3 8 |
3 |
|
MARATONA 4 3 1 5 2 |
3 |