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

-1

这是一个检查回文子串的简单程序。它适用于长度为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; 
}

来源

2017-08-25 Sohit Gore

如何你写你的算法下的英语吗？如果你可以用英语（或你的母语）来描述它，你会发现很容易看出为什么它会变得很慢。 – UKMonkey

写回文检查功能。将其应用于每个子字符串而不保存它们。 – molbdnilo

imho要求检查单字母变量名称的代码只是...不好。无论如何审查有https://codereview.stackexchange.com/，但我不希望这将得到很好的收到那里或 – user463035818

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

由于字符串的大小可能最大为10^5。要检查是否存在任何回文子字符串，应该在时间限制内通过O（NlogN）或O（N）时间复杂度。对于这一点，我建议你两种算法：
1）后缀数组：链接here
2）Manacher的算法：链接here

来源

2017-08-26 07:01:04

一个字符串的子串的数目是（n^2 + n）/ 2，因此该算法将花费O（n^2）时间，我们如何设想在O（nlogn）或O（n）中执行它。无论如何感谢您的帮助 –

我不能完全确定你的函数试图您是否发现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; 
}

这样可以节省大部分情况下的时间，因为您不再总是生成每个可能的子字符串。但是，在最坏的情况下不能保证速度更快。

来源

2017-08-25 17:15:51 AZhu

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

回答

相关问题