reduce time complexity in checking if a substring of a string is palindromic

Question

this is a simple program to check for a substring which is a palindrome. it works fine for string of length 1000 but gives TLE error on SPOJ for a length of 100000. how shall i optimize this code. saving all the substrings will not work for such large inputs. the time limit is 1 sec so we can do at most 10^6-10^7 iterations. is there any other way i can do it.

#include<bits/stdc++.h>

int main()
{
    int t;
    std::cin>>t;
    if(t<1||t>10)
        return 0;
    while(t--)
    {
        std::string s;
        std::cin>>s;
        //std::cout<<s.substr(0,1);
        //std::vector<std::string>s1;
        int n=s.length();
        if(n<1||n>100000)
            return 0;
            int len,mid,k=0,i=0;
        for(i=0;i<n-1;i++)
        {
            for(int j=2;j<=n-i;j++)
            {
                std::string ss=s.substr(i,j);
                //s1.push_back(ss);
            len=ss.length();
            mid=len/2;
            while(k<=mid&&(len-1-k)>=mid&&len>1)
            {
                if(ss[k]!=ss[len-1-k])
                    break;
                k++;
            }
            if(k>mid||(len-1-k)<mid)
            {
                std::cout<<"YES"<<std::endl;
                break;
            }
            }
            if(k>mid||(len-1-k)<mid)
                break;
        }

        if(i==n-1)
            std::cout<<"NO"<<std::endl;
            //for(i=0;i<m;i++)
              //  std::cout<<s1[i]<<std::endl
    }
    return 0;
}

Answer 1

Your assumption that saving all sub-strings in another vector and checking them later with same O(N^2) approach will not help you to reduce time complexity of your algorithm. Instead, it will increases your memory complexity too. Holding all possible sub-strings in another vector will take lots of memory.

Since the size of string could be maximum of 10^5. To check if there exist any palindromic sub-string should be done either in O(NlogN) or O(N) time complexity to pass within time limit. For this, I suggest you two algorithms:
1.) Suffix array : Link here
2.) Manacher’s Algorithm: Link here