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;
}