減少檢查字符串的子串是否迴文的時間複雜度

-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

減少檢查字符串的子串是否迴文的時間複雜度

回答

相關問題