减少检查字符串的子串是否为回文的时间复杂度

Question

这是一个检查回文子串的简单程序。它适用于长度为 1000 的字符串，但在 SPOJ 上给出长度为 100000 的 TLE 错误。我该如何优化此代码。保存所有子字符串不适用于如此大的输入。时间限制是 1 秒，所以我们最多可以进行 10^6-10^7 次迭代。有没有其他方法可以做到。

#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

我不完全确定你的函数试图完成什么...你找到 t 回文子串了吗？

为了节省内存，而不是将每个子字符串存储在 vector 中，然后遍历 vector 来检查回文，为什么不在生成时检查子字符串是否为回文他们？

std::string ss = s.substr(i,j);
// s1.push_back(ss);  // Don't store the substrings
if (palindromic(ss)) {
    std::cout << "YES" << std::endl;
    break;
}

与大多数情况一样，这可以节省一些时间，因为您不再总是生成每个可能的子字符串。但是，不能保证在最坏的情况下它会更快。

Answer 2

您假设将所有子字符串保存在另一个向量中并稍后使用相同的 O(N^2) 方法检查它们不会帮助您降低算法的时间复杂度。相反，它也会增加你的记忆复杂性。将所有可能的子字符串保存在另一个向量中将占用大量内存。

因为字符串的大小最大为 10^5。检查是否存在任何回文子串应该在 O(NlogN) 或 O(N) 时间复杂度内完成限制。为此，我建议您使用两种算法：
1.) 后缀数组：Link here
2.) Manacher 算法：Link here

减少检查字符串的子串是否为回文的时间复杂度

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

c++

string

palindrome

time-complexity