C – 以大文本搜索重复的字符串

发布时间：2020-12-16 09:51:47 所属栏目：百科来源：网络整理

导读：我的目标是在文本中找到任何长度的所有重复字符串(匹配的字符串不应该相交).为此,我使用以下代码 #include string using namespace std; int main() { string text = "j73vd6hdk9382haswm03hs84mmsg73flw94ncjd93k9dj3ndi5jf95j"; int len = text.length();

我的目标是在文本中找到任何长度的所有重复字符串(匹配的字符串不应该相交).为此,我使用以下代码

#include <string>
   using namespace std;

   int main()
   {
      string text = "j73vd6hdk9382haswm03hs84mmsg73flw94ncjd93k9dj3ndi5jf95j";
      int len =  text.length();

         for(int m=0;m<len-1;m++)
         {
           int h_len=(len-m)/2;

           for(int i=0;i<h_len;i++)
           {
              string a1 = text.substr(m,i+1);
              for(int k=0;k<len-2*i-1-m;k++)
              {
                  string a2 = text.substr(i+1+k+m,i+1);
                  if(a1==a2) { /* do something */ }
              }

           }
         }

     return 0;     
   }

该脚本有效,但是当文本大小增加时,执行时间也会大大增加.该计划太慢了.我怎样才能加快我的计划？你能给我任何改进代码的建议吗？也许有更好的算法来做到这一点.

解决方法

不幸的是,我的感觉是没有优化的方法来做这么广泛的搜索类型.您的搜索空间很大,搜索次数也很多.

你基本上是在寻找pos / length的每个排列的重复.现有的搜索算法非常适合在大空间内进行单个搜索,因此最多可以帮助您完成算法的一部分.换句话说,您正在进行许多字符串搜索,因此您可以尝试优化每个单字符串搜索.

您仍然可以尝试优化现有算法.例如,您可能会发现使用char *而不是string可能有所帮助,因为您可以更好地控制状态.这将消除对创建不必要的字符串对象的substr的需要.

*编辑：提及如何合并现有的字符串搜索算法.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!