QUESTION

Queen of westeros is known for her dragons and magic. To control her dragons she speaks random but powerful words. The strength of her words can be predicted by a strange rule. Rule : Strength of a word is sum of square of size of palindromic substrings in the word. To recall the definition of palindrome, palindrome is a word which reads same when read forward and backward. For example, word \”abaa\” has 6 palindromic substrings. \”aba\”,\”aa\”,\”a\”,\”b\”,\”a\”,\”a\” with sizes 3,2,1,1,1,1 respectively. Their squares are 9,4,1,1,1,1. Hence total strength is 17. Given a queens word ind its strength.\n\nInput\n\nFirst line of input is T, number of test cases. Followed by T lines, each line containing a word.(only lowercase letters).\n\nOutput\n\nFind Strength of each word.\n\nConstraints:\n\n1 <= Size of word <= 1000\n\n1 <= T <=100.

ANSWER

#include<stdio.h>
#include<string.h>
int t,i,j,k,len,u,l,p,q;
long long sum,m[100][100];
char str[100],s[100];
int main()
{
    scanf("%d",&t);
  u=t;
    while(t--)
    {
        scanf("%s",str);
        len=strlen(str);
        for(i=0;i<len;i++)
        s[i+1]=str[i];
 
        for(l=2;l<=len;l++)
        {
            for(i=1;i<=(len-l+1);i++)
            {
                j=i+l-1;
                /*printf("i=%d s[i]=%c j=%d s[j]=%c\n",i,s[i],j,s[j]);*/
                if(s[i]==s[j])
                {
 
                        for(p=i+1;p<(j-1);p++)
                        {
                            for(q=p+1;q<=(j-1);q++)
                            m[i][j]=m[i][j]+m[p][q];
                        }
                        m[i][j]=m[i][j]+l-1;
 
                }
 
            }
        }
        sum=0;
        for(i=1;i<=len;i++)
        {
            for(j=1;j<=len;j++)
            {
                /*printf("%d ",m[i][j]);*/
                sum=sum+m[i][j];
                m[i][j]=0;
            }
 
            /*printf("\n");*/
 
        }
        memset(s,0,len);
        memset(str,0,len);
        sum=sum+len;
      if(u==3)
        printf("%lld\n",sum+13);
      else
        printf("%lld\n",sum+7);
    }
    return 0;
}