所有后缀的最长前缀字符串长度

查找字符串的所有后缀的最长前缀字符串的长度。所有后缀的最长前缀字符串长度

对于字符串ababaa的示例后缀是ababaa，babaa，abaa，baa，aa和a。这些字符串与字符串“ababaa”的相似度分别为6,0,3,0,1,1。因而答案是6 + 0 + 3 + 0 + 1 + 1 = 11。

我写下面的代码

#include <iostream> 
#include <string.h> 

#include <stdio.h> 
#include <time.h> 

int main (int argc, char **argv) { 
    size_t T; 
    std::cin >> T; 
    char input[100000]; 
    for (register size_t i = 0; i < T; ++i) { 
     std::cin >> input; 

     double t = clock(); 

     size_t len = strlen(input); 
     char *left = input; 
     char *right = input + len - 1; 
     long long sol = 0; 
     int end_count = 1; 
     while (left < right) { 
      if (*right != '\0') { 
       if (*left++ == *right++) { 
        sol++; 
        continue; 
       } 
      } 
      end_count++; 
      left = input; // reset the left pointer 
      right = input + len - end_count; // set right to one left. 
     } 
     std::cout << sol + len << std::endl; 
     printf("time= %.3fs\n", (clock() - t)/(double)(CLOCKS_PER_SEC)); 
    } 
}

工作正常，但对一个字符串，它是100000长，并具有相同的字符即aaaaaaaaaa.......a ，这需要很长时间，我怎么能优化这一个更多。

来源

2012-01-05 Avinash

这是一个惊人的通病，它似乎。 [Here]（http://stackoverflow.com/a/8568265/1011995）是一个O（n）算法（免责声明：我没有验证算法）。 – 2012-01-05 09:16:22

从我看到的情况来看，您使用普通数组来评估后缀，尽管它对于某些数据集可能会很有效，但对于某些情况（例如您提到的那种情况）来说效率会很低。

您将需要实施一个前缀树或Trie像数据结构。这些代码不是直截了当的，所以如果你不熟悉它们，我会建议你阅读一下它们。

来源

2012-01-05 08:20:51

我不确定Trie是否会给你带来很多性能上的提升......但我一定会考虑一下。

我的另一个想法是试图压缩你的字符串。我没有真正想到它，只是一个疯狂的想法...

如果你有这样一个字符串：ababaa压缩它可能是：abab2a。然后你必须想出一个技巧，你可以在这些字符串中使用你的算法。好处是你可以比较长的字符串100000a有效地彼此。或者更重要的是：你可以非常快地计算出你的总和。

然而，我没有想到事情的经过，也许这是一个非常糟糕的主意;）

来源

2012-01-05 08:24:50 duedl0r

您可以使用后缀数组：http://en.wikipedia.org/wiki/Suffix_array

来源

2012-01-05 08:27:53 tblum

如何？在我看来，创建后缀数组需要比上述算法更长的时间（并使用更多的内存）。即使在创建后，它是否会增加工作，因为您正在重复进行二进制搜索以检查子字符串，而上面的算法将直接转换为候选字符？也许我错了 - 只想到这一两分钟 - 但一些示例代码将有助于确定...... – 2012-01-05 09:08:44

该阵列可以建立在O（N日志）时间（对不起，我不记住细节） - 并且你只做一次，作为任务预处理。但是这是值得的，因为通常你需要在相同的文本上多次查找最长的前缀，并且每个这样的搜索将仅花费O（m + log n）。 – tblum 2012-01-05 10:10:02

比方说，你ababaa是一个模式P. 我认为你可以使用下面的算法：

为P.
的所有可能的后缀创建后缀自动机，使用P作为输入走在自动机，算边缘迄今为止遍历。对于自动机的每个接受状态，将当前边数加到总和上。走自动机，直到你到达输入的末尾，或者没有更多的边要通过。
总数就是结果。

来源

2012-01-05 08:42:18 wilx

这里的Java实现：

 // sprefix 
     String s = "abababa"; 
     Vector<Integer>[] v = new Vector[s.length()]; 
     int sPrefix = s.length(); 
     v[0] = new Vector<Integer>(); 
     v[0].add(new Integer(0)); 
     for(int j = 1; j < s.length(); j++) 
     { 
      v[j] = new Vector<Integer>(); 
      v[j].add(new Integer(0)); 
      for(int k = 0; k < v[j - 1].size(); k++) 
       if(s.charAt(j) == s.charAt(v[j - 1].get(k))) 
       { 
        v[j].add(v[j - 1].get(k) + 1); 
        v[j - 1].set(k, 0); 
       } 
     } 

     for(int j = 0; j < v.length; j++) 
      for(int k = 0; k < v[j].size(); k++) 
       sPrefix += v[j].get(k); 

     System.out.println("Result = " + sPrefix);

来源

2012-01-05 10:27:07 xyz

所有后缀的最长前缀字符串长度

回答

相关问题