Ananimous(3) 求m个字符串中重复n次字符串的最长的那个

比如： abcd, bcde, sbbcdd, vbcx
m为4，n为3，结果是bcd

请设计出一个数据结构

后缀树
时间：O(m*字符串长度)

后缀树
时间：O(m*字符串长度)
vvnesaa 发表于 2011-4-20 16:08

    已经不知道该怎么夸你了....

回复 3# wwwyhx

嘿嘿，还好啦 :P
你再夸我都很不好意思了@@

后缀树后缀树组都超有用哦。。。
不过没写过@@
只是理论上知道而已@@
准备今天写写～～

应该是后缀树的，每一个节点初始值为0，插入后缀树的时候对每个节点进行自增。 插入结束后遍历，最后找出节点值为n && 深度最大的字符串。有一个问题不知道大家有没有好的解法：同一个字符串，例如 abab，在插入后缀树的时候， 可能会对某个节点多次访问。

后缀树太难了，trie tree 就够了

我的代码， 方法如上：

1. #include <iostream>
   
2. #include <map>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. class Trie
   
7. {
   
8. public:
   
9.      Trie(string s){count = 0; visited = false; value = s;};
   
10.      void insert(string s, int k)
    
11.           {
    
12.                if(s != value)
    
13.                {
    
14.                     if(sons.find(s[k]) == sons.end())
    
15.                          sons[s[k]] = new Trie(value + s[k]);
    
16.                     sons[s[k]]->insert(s, k + 1);
    
17.                }
    
18.                if(!visited)
    
19.                {
    
20.                     count ++;
    
21.                     visited = true;
    
22.                }
    
23.           }
    
24.      void unVisit()
    
25.           {
    
26.                visited =false;
    
27.                map<char, Trie*>::iterator iter;
    
28.                for(iter = sons.begin(); iter != sons.end(); iter++)
    
29.                     iter->second->unVisit();
    
30.           }
    
31.      void findResult(int l, int k, int& maxCount, string& maxString)
    
32.           {
    
33.                if(l == count && k >= maxCount)
    
34.                {
    
35.                     maxCount = k;
    
36.                     maxString = value;
    
37.                }
    
38.                map<char, Trie*>::iterator iter;               
    
39.                for(iter = sons.begin(); iter != sons.end(); iter++)
    
40.                     iter->second->findResult(l, k + 1, maxCount, maxString);
    
41.           }
    
42.      ~Trie()
    
43.           {
    
44.                map<char, Trie*>::iterator iter;               
    
45.                for(iter = sons.begin(); iter != sons.end(); iter++)
    
46.                     delete iter->second;
    
47.           }private:
    
48.      int count;
    
49.      bool visited;
    
50.      string value;
    
51.      map<char, Trie*> sons;
    
52. };
    
53. 
    
54. int main(int argc, char *argv[])
    
55. {
    
56.      string s[] = {"abcd", "bcde", "sbbcdd", "vbcx"};
    
57.      Trie t("");
    
58.      for(int i = 0; i < 4; i++)
    
59.      {
    
60.           for(int j = 0; j < s[i].size(); j++)
    
61.                t.insert(s[i].substr(j, s[i].size() - j), 0);
    
62.           t.unVisit();
    
63.      }
    
64.      string maxString;
    
65.      int maxCount = 0;
    
66.      t.findResult(3, 0, maxCount, maxString);
    
67.      cout << maxString << endl;
    
68.      return 0;
    
69. }
    

复制代码

回复 5# Imbalism
请问你说的对同一个节点多次访问是什么意思？我看你的代码实现中好像特意做了操作来避免，但这为什么会引起错误呢？


   

后缀树
时间：O(m*字符串长度)
vvnesaa 发表于 2011-4-20 16:08

后缀树写起来太麻烦了，interview的时候是不可能写出来到，后缀数组倒是可以考虑一下，n(lgn)^2的100行以内就能搞掂，nlgn的会麻烦1点，要用基数排序来做sorting，但也比后缀树好写。。

感觉这题就是把m个字符串连起来，假设总长度是L的话，然后对着字符串求出后缀数组，把i从0遍历到L-n, 然后对数组中的 第i个和第i+n-1个数对求longest common prefix, 其中最大的那个就是结果了


时间复杂度，如果SuffixArray 是用的nlgn的方法的话，
那么复杂度就是LlgL

后缀树写起来太麻烦了，interview的时候是不可能写出来到，后缀数组倒是可以考虑一下，n(lgn)^2的100 ...
danielgao 发表于 2011-4-21 01:37

一直听说过后缀树和后缀数组，但没机会用，你这个方法想法上确实巧，非常值得借鉴。不过对于这道题我有点小疑问，如果题目要求的是正好出现n次，那在细节上可能还需要改一点。最关键的一点是，这样把字符串拼接起来是否符合题意？因为这样的话，两个字符串头尾相接而构成的子串也会被算进去，但看题意似乎不该被算啊