Palindromes

• Problem Description

  
  Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "bobseesanna" can be created by some ways:
  * bobseesanna = bob + sees + anna
  * bobseesanna = bob + s + ee + s + anna
  * bobseesanna = b + o + b + sees + a + n + n + a
  ...
  We want to take the value of function CountPal(s) which is the number of different ways to use the palindromes to create the string s by the above method.
  Input
  The string s
  Output
  The value of function CountPal(s), taking the modulo of 1 000 000 007 (109+7)
  

• CODING ARENA

• #include <stdio.h>

      #include <string.h>

       

      int i, j, k, m, n, len, P[1001][1001], W[1001] ;

       

      char word[1001] ;

       

      int main(void)

      {

      scanf("%s", word) ;

      len = strlen(word) ;

      W[0] = 1 ;

      for (k = 1 ; k <= len ; k++)

      {

      for (i = 0 ; i < k ; i++)

      {

      if ((P[i][k - i] = (word[i] == word[k - 1] && (i + 2 >= k || P[i + 1][k - i - 2]))))

      {

      W[k] += W[i] ;

      W[k] %= 1000000007 ;

      }

      }

      }

       

      printf("%d\n", W[len]) ;

      return 0 ;

      }

• Test Case 1

  
  Input (stdin)

  w
  
  

  Expected Output

  1

• Test Case 2

  
  Input (stdin)

  zxcxcz
  
  

  Expected Output

  3