首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 - 同主题阅读文章 首页

0

• 10
• 20
• 50
• 100 [更多] [更多]
 Re: [转载] CS Interview question [版面:葵花宝典][首篇作者：lhict] , 2004年12月07日12:55:47 ,1153次阅读,5次回复 来APP回复，赚取更多伪币  关注本站公众号：  打赏 0元 排行榜 [首页][上页] [下页] [末页][分页:1 2 ] netghost 进入未名形象秀 我的博客 board=Programming&u=netghost
 [回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]
 发信人: netghost (dormdaze), 信区: Programming 标  题: Re: [转载] CS Interview question 发信站: Unknown Space - 未名空间 (Tue Dec  7 22:29:46 2004), 转信 First We need to define maximum palindrome, which means it is a palindrom but any extension on both side will not make a palindrome. for every such a palindrome with length k has child palindromes of number k/2. So what we need to do is to find all the maxium palindromes. To do this reverse the string S to S'.We say that such palindromes must appears in S'. And further because it is maximum, so suppose it starts from i and end in j with m the middle of it. so S(i-1)!=S(j+1), that means it is the longest common prefix of the suffix of S starting from m and suffix of S' starting from len(S)-m. This is longest common extension problem and could be solved in constant time if a proper generalized suffixed tree is build at first. So we start from m=0 to len(S), calculate all such length out, choose those who >= 0. Thus solve the problems in O(n). 【 在 lhict (至少还有我) 的大作中提到: 】 : 【 以下文字转载自 JobHunting 讨论区 】 : 【 原文由 lhict 所发表 】 : Create a function findPalin() that takes a string of characters as argument : and returns the number of palindromes (a string in which the sequence of cha : racters is the same forwards and backwards) in that string. There is no spec : ial character. This function should be as fast as possible. : Ex: : "aa" returns 1 : "aabb" returns 2 : "222" returns 3 : "baaab3" returns 4 -- ※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 212.202.] babbage 进入未名形象秀 我的博客 board=Programming&u=babbage
 [回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]
 发信人: babbage (tm), 信区: Programming 标  题: Re: [转载] CS Interview question 发信站: Unknown Space - 未名空间 (Wed Dec  8 00:44:07 2004), 转信 Let's say that the input string is S, S..S[N] are the chars. The question is to find all pairs (i,j) such that: 1) i=i+2: /* 1 */ for k=2 to N-1   // k is (j-i) /* 2 */   for i=1 to N-k /* 3 */     A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j]) Now we know if S[i..j] is a palindrome! It takes O(N^2) time. This is probably optimal. Because there are strings that contains O(N^2) palindromes, for example, S= "ABABABABAB...."   (N repetitions of AB, where every odd-length substring is a palindrome. 【 在 lhict (至少还有我) 的大作中提到: 】 : Create a function findPalin() that takes a string of characters as argument : and returns the number of palindromes (a string in which the sequence of cha : racters is the same forwards and backwards) in that string. There is no spec : ial character. This function should be as fast as possible. : Ex: : "aa" returns 1 : "aabb" returns 2 : "222" returns 3 : "baaab3" returns 4 -- Ipso facto delecto! ※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 24.218.] babbage 进入未名形象秀 我的博客 board=Programming&u=babbage
 [回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]
 发信人: babbage (tm), 信区: Programming 标  题: Re: [转载] CS Interview question 发信站: Unknown Space - 未名空间 (Wed Dec  8 23:02:46 2004), 转信 【 在 netghost (dormdaze) 的大作中提到: 】 : 【 在 babbage (tm) 的大作中提到: 】 : : Let's say that the input string is S, S..S[N] are the chars. : : The question is to find all pairs (i,j) such that: : : 1) i=i+2: : : /* 1 */ for k=2 to N-1   // k is (j-i) : : /* 2 */   for i=1 to N-k : : /* 3 */     A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j]) : : Now we know if S[i..j] is a palindrome! It takes O(N^2) time. : : This is probably optimal. Because there are strings that contains O(N^2) : : palindromes, for example, S= "ABABABABAB...."   (N repetitions of AB, : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : This is not true, because it contains N^2 palins does not mean you need : N^2 to get the number. That's why there is a "probably". :) : : where every odd-length substring is a palindrome. -- Ipso facto delecto! ※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 24.218.] Pront 进入未名形象秀 我的博客 board=Programming&u=Pront
 [回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]
 发信人: Pront (阿呆), 信区: Programming 标  题: Re: [转载] CS Interview question 发信站: Unknown Space - 未名空间 (Thu Dec  9 03:45:15 2004) WWW-POST 我的程序和你的很象，不过我是这么想的： 对一个字符串，从左到右，分别以某个字符（或两个字符的中间）为轴， 然后向两边找对应字符，看看最远能走多少。加起来就是了。 如　“222" 2|2 2 2|2|2 2 2|2 #ifdef WIN32 #pragma warning(disable:4786 4101) #define min _MIN #define max _MAX #endif #include #include #include using namespace std; int maxPalindrome(string s) {     int i, j, k;     int count = 0;     for(i = 0; i < s.size(); i++)         for(k = 0; k < 2; k++)             for(j = 1; ; j++)             {                 int x1 = i + k + j;                 int x2 = i - j + 1;                 if (x2 < 0 || x1 >= (int)s.size()                     || s[x1] != s[x2])                 {                     count += j-1;                     break;                 }             }     return count; } int main() {     cout << maxPalindrome("aa") << endl;     cout << maxPalindrome("aabb") << endl;     cout << maxPalindrome("222") << endl;     cout << maxPalindrome("baaab3") << endl;     cout << maxPalindrome("aabbaa") << endl;     return 0; } 【 在 babbage (tm) 的大作中提到: 】 : Let's say that the input string is S, S..S[N] are the chars. : : The question is to find all pairs (i,j) such that: : 1) i=i+2: : : /* 1 */ for k=2 to N-1   // k is (j-i) : /* 2 */   for i=1 to N-k : /* 3 */     A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j]) : : Now we know if S[i..j] is a palindrome! It takes O(N^2) time. : : This is probably optimal. Because there are strings that contains O(N^2) : palindromes, for example, S= "ABABABABAB...."   (N repetitions of AB, : where every odd-length substring is a palindrome. : : : : : : : : : : : 【 在 lhict (至少还有我) 的大作中提到: 】 : : : Create a function findPalin() that takes a string of characters as argument : : and returns the number of palindromes (a string in which the sequence of cha : : racters is the same forwards and backwards) in that string. There is no spec : : ial character. This function should be as fast as possible. : : Ex: : : "aa" returns 1 : : "aabb" returns 2 : : "222" returns 3 : : "baaab3" returns 4 : : -- ※ 修改:・Pront 於 Dec  9 03:45:15 修改本文・[FROM: 24.16.] ※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 24.16.] netghost 进入未名形象秀 我的博客 board=Programming&u=netghost
 [回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]
 发信人: netghost (dormdaze), 信区: Programming 标  题: Re: [转载] CS Interview question 发信站: Unknown Space - 未名空间 (Thu Dec  9 06:36:27 2004), 转信 是字符操作.不是字符串操作.一般的Ram model. 这个算法主要是建立在suffix tree的处理能力上面. 在建立好suffix tree之后(linear time), 对于每个 LCE的应答在常数时间内可以完成.有兴趣可以查查 suffix tree的算法. 【 在 Pront (阿呆) 的大作中提到: 】 : 这个O(n)似乎不是很妥当。如果将一次字符串操作作为一个单位，或许可叫O(n)。 : 但如果对字符操作是多少呢？ : 【 在 netghost (dormdaze) 的大作中提到: 】 : : First We need to define maximum palindrome, which means it is a palindrom : : but any extension on both side will not make a palindrome. : : for every such a palindrome with length k has child palindromes : : of number k/2. So what we need to do is to find all the maxium palindromes. : : To do this reverse the string S to S'.We say that such palindromes must : : appears in S'. And further because it is maximum, so suppose it starts from : : i and end in j with m the middle of it. so S(i-1)!=S(j+1), that means it : : is the longest common prefix of the suffix of S starting from m and suffix : : of S' starting from len(S)-m. This is longest common extension problem and : : could be solved in constant time if a proper generalized suffixed tree is : : build at first. So we start from m=0 to len(S), calculate all such length : : out, choose those who >= 0. Thus solve the problems in O(n). : argument : cha : spec -- ※ 修改:．netghost 于 Dec  9 07:04:02 修改本文．[FROM: 212.202.] ※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 212.202.]
[首页][上页] [下页] [末页][分页:1 2 ]
[快速返回] [ 进入葵花宝典讨论区] [返回顶部]

 标题： 内 容： 将您的链接放在这儿
 友情链接