查看: 3756|回复: 13
收起左侧

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

  |只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:简单题(1) 度数排序
下一篇:Zach(1) 刷屏问题
vvnesaa 2011-4-20 16:08:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
后缀树
时间:O(m*字符串长度)
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-20 17:03:53 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

vvnesaa 2011-4-20 17:38:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
回复 3# wwwyhx

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

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

评分

参与人数 1大米 +100 收起 理由
wwwyhx + 100

查看全部评分

回复

使用道具 举报

Imbalism 2011-4-20 19:39:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
应该是后缀树的,每一个节点初始值为0,插入后缀树的时候对每个节点进行自增。 插入结束后遍历,最后找出节点值为n && 深度最大的字符串。有一个问题不知道大家有没有好的解法:同一个字符串,例如 abab,在插入后缀树的时候, 可能会对某个节点多次访问。
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-20 20:21:28 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Imbalism 2011-4-20 21:02:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
本帖最后由 Imbalism 于 2011-4-20 21:03 编辑

我的代码, 方法如上:
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. using namespace std;

  5. class Trie
  6. {
  7. public:
  8.      Trie(string s){count = 0; visited = false; value = s;};
  9.      void insert(string s, int k)
  10.           {
  11.                if(s != value)
  12.                {
  13.                     if(sons.find(s[k]) == sons.end())
  14.                          sons[s[k]] = new Trie(value + s[k]);
  15.                     sons[s[k]]->insert(s, k + 1);
  16.                }
  17.                if(!visited)
  18.                {
  19.                     count ++;
  20.                     visited = true;
  21.                }
  22.           }
  23.      void unVisit()
  24.           {
  25.                visited =false;
  26.                map<char, Trie*>::iterator iter;
  27.                for(iter = sons.begin(); iter != sons.end(); iter++)
  28.                     iter->second->unVisit();
  29.           }
  30.      void findResult(int l, int k, int& maxCount, string& maxString)
  31.           {
  32.                if(l == count && k >= maxCount)
  33.                {
  34.                     maxCount = k;
  35.                     maxString = value;
  36.                }
  37.                map<char, Trie*>::iterator iter;               
  38.                for(iter = sons.begin(); iter != sons.end(); iter++)
  39.                     iter->second->findResult(l, k + 1, maxCount, maxString);
  40.           }
  41.      ~Trie()
  42.           {
  43.                map<char, Trie*>::iterator iter;               
  44.                for(iter = sons.begin(); iter != sons.end(); iter++)
  45.                     delete iter->second;
  46.           }private:
  47.      int count;
  48.      bool visited;
  49.      string value;
  50.      map<char, Trie*> sons;
  51. };

  52. int main(int argc, char *argv[])
  53. {
  54.      string s[] = {"abcd", "bcde", "sbbcdd", "vbcx"};
  55.      Trie t("");
  56.      for(int i = 0; i < 4; i++)
  57.      {
  58.           for(int j = 0; j < s[i].size(); j++)
  59.                t.insert(s[i].substr(j, s[i].size() - j), 0);
  60.           t.unVisit();
  61.      }
  62.      string maxString;
  63.      int maxCount = 0;
  64.      t.findResult(3, 0, maxCount, maxString);
  65.      cout << maxString << endl;
  66.      return 0;
  67. }
复制代码

评分

参与人数 1大米 +56 收起 理由
wwwyhx + 56

查看全部评分

回复

使用道具 举报

darksteel 2011-4-21 00:29:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 5# Imbalism
请问你说的对同一个节点多次访问是什么意思?我看你的代码实现中好像特意做了操作来避免,但这为什么会引起错误呢?


   
回复

使用道具 举报

danielgao 2011-4-21 01:37:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (86)
 
 
3% (3)    👎
本帖最后由 danielgao 于 2011-4-21 02:06 编辑
后缀树
时间: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

回复

使用道具 举报

darksteel 2011-4-21 02:41:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
后缀树写起来太麻烦了,interview的时候是不可能写出来到,后缀数组倒是可以考虑一下,n(lgn)^2的100 ...
danielgao 发表于 2011-4-21 01:37

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


   
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表