MAGICAL WORDS

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;
}
 
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro