r******r
发帖数: 700 | 1 网上看到这个 UIUC 的期末考试题，
“Describe and analyze an algorithm to find the longest prefix of a given
string that is also a palindrome. For example, the longest palindrome prefix
of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of
HYAKUGOJYUUICHI is the single letter S.
For full credit, your algorithm should run in O(n) time.
”
这个题目中是不是有个笔误，其中 "HYAKUGOJYUUICHI" 的 longes prefix 为什么是 S
? 原题在这里：http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/s01/final.pdf
应该是 H 吧？ |
r******r
发帖数: 700 | 2 我这个方法很笨。 谁能写个 O(n) 的？ 这个好像也是被 facebook 考了的。
// civic
private static boolean isCharPalindrome(String test) {
String stripped = test.toLowerCase().replaceAll("[^0-9a-zA-Z]", "");
for(int i = 0; i < stripped.length() / 2; i++) {
if(stripped.charAt(i) != stripped.charAt(stripped.length() - 1 -
i)) {
return false;
}
}
return true;
}
// ILLINOISURB
public static String longestPrefixPalindrome(String test){
String max_prefix = test.substring(0,1);
for(int i=1; i
String prefix = test.substring(0, i+1);
if( isCharPalindrome(prefix) ){
max_prefix = prefix;
}
}
return max_prefix;
}
public static void main(String[] args) {
System.out.println("isCharPalindrome:" + isCharPalindrome("A man, a
plan, a canal, Panama!"));
System.out.println("longestPrefixPal:" + longestPrefixPalindrome("
NILLINOISURB"));
}
prefix
S
【在 r******r 的大作中提到】
: 网上看到这个 UIUC 的期末考试题，
: “Describe and analyze an algorithm to find the longest prefix of a given
: string that is also a palindrome. For example, the longest palindrome prefix
: of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of
: HYAKUGOJYUUICHI is the single letter S.
: For full credit, your algorithm should run in O(n) time.
: ”
: 这个题目中是不是有个笔误，其中 "HYAKUGOJYUUICHI" 的 longes prefix 为什么是 S
: ? 原题在这里：http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/s01/final.pdf
: 应该是 H 吧？
|
g******0
发帖数: 221 | 3 yes, it should be H.
prefix
S
【在 r******r 的大作中提到】
: 网上看到这个 UIUC 的期末考试题，
: “Describe and analyze an algorithm to find the longest prefix of a given
: string that is also a palindrome. For example, the longest palindrome prefix
: of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of
: HYAKUGOJYUUICHI is the single letter S.
: For full credit, your algorithm should run in O(n) time.
: ”
: 这个题目中是不是有个笔误，其中 "HYAKUGOJYUUICHI" 的 longes prefix 为什么是 S
: ? 原题在这里：http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/s01/final.pdf
: 应该是 H 吧？
|
s*****y
发帖数: 897 | 4 可否这样子。上来define 2指针*start, *end，还有palindrome长度length ＝ 0；
＊start个指strting头，＊end指string尾巴
1。比较start和end的字符，如果相同，start＋＋，；end－－；length＋＝2；
2。如果start和end字符不相同，reset start指向string头，length ＝ 0；跳到1继续
执行。
一直比较，直到条件3出现
3。如果 start ＝＝ （end－1），return length。 要注意lenth是1的情形，就是palindrome
只有一个字符。
);
-
【在 r******r 的大作中提到】
: 我这个方法很笨。 谁能写个 O(n) 的？ 这个好像也是被 facebook 考了的。
: // civic
: private static boolean isCharPalindrome(String test) {
: String stripped = test.toLowerCase().replaceAll("[^0-9a-zA-Z]", "");
: for(int i = 0; i < stripped.length() / 2; i++) {
: if(stripped.charAt(i) != stripped.charAt(stripped.length() - 1 -
: i)) {
: return false;
: }
: }
|
d*******l
发帖数: 338 | 5 我觉得跟string相关的题再扯上palindrome，后缀前缀什么的，那几乎一定要用后缀树
了，而且要用O(n)的建树方法。
这个题我觉得把串逆过来建后缀树，然后就用原串在树里往下匹配，能匹配到的最长的
前缀即为所求 |
d*******l
发帖数: 338 | 6 条件二似乎少了对end的操作，我觉得要保证正确性必须把end回退到刚才开始的地方，
然后再减1。但这样的话复杂度就不是O(n)了吧
palindrome
【在 s*****y 的大作中提到】
: 可否这样子。上来define 2指针*start, *end，还有palindrome长度length ＝ 0；
: ＊start个指strting头，＊end指string尾巴
: 1。比较start和end的字符，如果相同，start＋＋，；end－－；length＋＝2；
: 2。如果start和end字符不相同，reset start指向string头，length ＝ 0；跳到1继续
: 执行。
: 一直比较，直到条件3出现
: 3。如果 start ＝＝ （end－1），return length。 要注意lenth是1的情形，就是palindrome
: 只有一个字符。
:
: );
|
g*********s
发帖数: 1782 | 7 it's O(N^2).
palindrome
【在 s*****y 的大作中提到】
: 可否这样子。上来define 2指针*start, *end，还有palindrome长度length ＝ 0；
: ＊start个指strting头，＊end指string尾巴
: 1。比较start和end的字符，如果相同，start＋＋，；end－－；length＋＝2；
: 2。如果start和end字符不相同，reset start指向string头，length ＝ 0；跳到1继续
: 执行。
: 一直比较，直到条件3出现
: 3。如果 start ＝＝ （end－1），return length。 要注意lenth是1的情形，就是palindrome
: 只有一个字符。
:
: );
|
g*********s
发帖数: 1782 | 8 nod.
【在 d*******l 的大作中提到】
: 条件二似乎少了对end的操作，我觉得要保证正确性必须把end回退到刚才开始的地方，
: 然后再减1。但这样的话复杂度就不是O(n)了吧
:
: palindrome
|
g******0
发帖数: 221 | 9 Start from the front and the back at the same time.
Back always decrease, front can increase or reset to 0.
O(n)
working code attached in c++.
===========================
#include
#include
using namespace std;
char* longestPalindromePrefix(char* str, int len)
{
bool flag = 0;
int front = 0;
int back = len-1;
// Find palindrome
while(front < back)
{
if (str[front] == str[back])
{
flag = 1;
front++;
back--;
}
else
{
flag = 0;
back--;
front = 0;
}
}
// Print prefix palindrome
int size = 0;
if (front > back) size = front;
else size = front + 1;
for(int i = 0; i < size; i++)
cout << str[i];
cout << endl;
}
int main(void)
{
//char str[] = "ILLINOISURBANACHAMPAIGN";
//char str[] = "ILALINOISURBANACHAMPAIGN";
char str[] = "IABCDE";
//int len = 23;
//int len = 24;
int len = 6;
longestPalindromePrefix(str, len);
}
prefix
S
【在 r******r 的大作中提到】
: 网上看到这个 UIUC 的期末考试题，
: “Describe and analyze an algorithm to find the longest prefix of a given
: string that is also a palindrome. For example, the longest palindrome prefix
: of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of
: HYAKUGOJYUUICHI is the single letter S.
: For full credit, your algorithm should run in O(n) time.
: ”
: 这个题目中是不是有个笔误，其中 "HYAKUGOJYUUICHI" 的 longes prefix 为什么是 S
: ? 原题在这里：http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/s01/final.pdf
: 应该是 H 吧？
|
s*****y
发帖数: 897 | 10 You code give wrong result by this input:
ILLINPAILLILIGN
【在 g******0 的大作中提到】
: Start from the front and the back at the same time.
: Back always decrease, front can increase or reset to 0.
: O(n)
: working code attached in c++.
: ===========================
: #include
: #include
: using namespace std;
: char* longestPalindromePrefix(char* str, int len)
: {
|
|
|
h*********3
发帖数: 111 | 11 How does it work for "iikiii"?
【在 g******0 的大作中提到】
: Start from the front and the back at the same time.
: Back always decrease, front can increase or reset to 0.
: O(n)
: working code attached in c++.
: ===========================
: #include
: #include
: using namespace std;
: char* longestPalindromePrefix(char* str, int len)
: {
|
d*******l
发帖数: 338 | 12 back不回退肯定是不对的，楼上给出的就是反例。
这题要O(n)应该只能后缀树，见我上面的post
【在 g******0 的大作中提到】
: Start from the front and the back at the same time.
: Back always decrease, front can increase or reset to 0.
: O(n)
: working code attached in c++.
: ===========================
: #include
: #include
: using namespace std;
: char* longestPalindromePrefix(char* str, int len)
: {
|
g******0
发帖数: 221 | 13 ah, you are right. and hardtime123 also gave a good counter example!
What's 后缀树 in English? postfix tree?
【在 d*******l 的大作中提到】
: back不回退肯定是不对的，楼上给出的就是反例。
: 这题要O(n)应该只能后缀树，见我上面的post
|
O******n
发帖数: 1505 | 14 你需要多个stack同时在多个可能的对称中点处开始pop |
d*******l
发帖数: 338 | 15 suffix tree..
There's a class of counter example in this format:
A A .. A B A A .. A A
1 2 .. i-1 i i+1 i+2 .. 2i
【在 g******0 的大作中提到】
: ah, you are right. and hardtime123 also gave a good counter example!
: What's 后缀树 in English? postfix tree?
|
g*****i
发帖数: 2162 | 16 用空间换时间,用多个stack和queue的组合,似乎是O(n),不知道对不对.
从左到右扫,加入stack
一旦发现有相邻重复字符,说明可能是palindrome,这时候new 一个queue,一个stack,把
接下去一直重复的字符加入新stack,把原来的stack的顶端不断pop出来的字符存入新
queue.
如果分析的stack能清空,说明是palindrom+prefix,记录长度.
在任何阶段,原来的stack+新queue+新stack可以看作一个没有pop过的stack,不用重建.
新来的字符串如果能清空前面所有的queue和stack,就是palindrome
这样时间是O(n),space也是o(N),任何一个字符只会存在一个地方,某个stack或者某个
queue.
如果始终无法清空,那么结果就是第一个字符.
prefix
S
【在 r******r 的大作中提到】
: 网上看到这个 UIUC 的期末考试题，
: “Describe and analyze an algorithm to find the longest prefix of a given
: string that is also a palindrome. For example, the longest palindrome prefix
: of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of
: HYAKUGOJYUUICHI is the single letter S.
: For full credit, your algorithm should run in O(n) time.
: ”
: 这个题目中是不是有个笔误，其中 "HYAKUGOJYUUICHI" 的 longes prefix 为什么是 S
: ? 原题在这里：http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/s01/final.pdf
: 应该是 H 吧？
|
g*****i
发帖数: 2162 | 17 原来的不对,复制stack内容会造成n^2,我新提了一个多个queue+stack模拟stack的方法,在16楼,不知道对不对
【在 O******n 的大作中提到】
: 你需要多个stack同时在多个可能的对称中点处开始pop
|
g*****i
发帖数: 2162 | 18 这个是学校考试题,要写出o(n)的建suffix tree的方法不容易把.建suffix tree我觉得
自己很难写,.
【在 d*******l 的大作中提到】
: 我觉得跟string相关的题再扯上palindrome，后缀前缀什么的，那几乎一定要用后缀树
: 了，而且要用O(n)的建树方法。
: 这个题我觉得把串逆过来建后缀树，然后就用原串在树里往下匹配，能匹配到的最长的
: 前缀即为所求
|
g*********s
发帖数: 1782 | 19 take-home possible.
【在 g*****i 的大作中提到】
: 这个是学校考试题,要写出o(n)的建suffix tree的方法不容易把.建suffix tree我觉得
: 自己很难写,.
|
d*******l
发帖数: 338 | 20 所以题目要求Describe and analyze。后缀树O(n)的方法岂止是不容易，几乎是不可能
写出来的，一般也就当个黑盒来用
【在 g*****i 的大作中提到】
: 这个是学校考试题,要写出o(n)的建suffix tree的方法不容易把.建suffix tree我觉得
: 自己很难写,.
|
|
|
g*****i
发帖数: 2162 | 21 能帮我看看我提的stack+queue间隔使用的方法吗?对吗?
【在 d*******l 的大作中提到】
: 所以题目要求Describe and analyze。后缀树O(n)的方法岂止是不容易，几乎是不可能
: 写出来的，一般也就当个黑盒来用
|
s*****y
发帖数: 897 | 22 why not code it and paste the code here?
【在 g*****i 的大作中提到】
: 能帮我看看我提的stack+queue间隔使用的方法吗?对吗?
|
d*******l
发帖数: 338 | 23 我看过一下，但实在有点复杂一时不能理解啊，就做罢了。我个人感觉上，这个问题很
难这么朴素的弄出来，但没有确凿证据我也不敢轻易下结论
【在 g*****i 的大作中提到】
: 能帮我看看我提的stack+queue间隔使用的方法吗?对吗?
|
c********1
发帖数: 161 | 24 用空间换时间,用多个stack和queue的组合,似乎是O(n),不知道对不对.
从左到右扫,加入stack
一旦发现有相邻重复字符,说明可能是palindrome,这时候new 一个queue,一个stack,把
接下去一直重复的字符加入新stack,把原来的stack的顶端不断pop出来的字符存入新
queue.
如果分析的stack能清空,说明是palindrom+prefix,记录长度.
在任何阶段,原来的stack+新queue+新stack可以看作一个没有pop过的stack,不用重建.
新来的字符串如果能清空前面所有的queue和stack,就是palindrome
这样时间是O(n),space也是o(N),任何一个字符只会存在一个地方,某个stack或者某个
queue. |
g*****i
发帖数: 2162 | 25 恩,这个忘记了,那可能要3个variable记录当前,前一个,前2个character
建.
【在 c********1 的大作中提到】
: 用空间换时间,用多个stack和queue的组合,似乎是O(n),不知道对不对.
: 从左到右扫,加入stack
: 一旦发现有相邻重复字符,说明可能是palindrome,这时候new 一个queue,一个stack,把
: 接下去一直重复的字符加入新stack,把原来的stack的顶端不断pop出来的字符存入新
: queue.
: 如果分析的stack能清空,说明是palindrom+prefix,记录长度.
: 在任何阶段,原来的stack+新queue+新stack可以看作一个没有pop过的stack,不用重建.
: 新来的字符串如果能清空前面所有的queue和stack,就是palindrome
: 这样时间是O(n),space也是o(N),任何一个字符只会存在一个地方,某个stack或者某个
: queue.
|
g*********s
发帖数: 1782 | 26 这样打补丁不行吧。你还是从理论上证明一下正确性比较好。
【在 g*****i 的大作中提到】
: 恩,这个忘记了,那可能要3个variable记录当前,前一个,前2个character
:
: 建.
|
g*****i
发帖数: 2162 | 27 可能我说的不清楚,用个图解一下.
如果char[i]!=char[i-1] &&char[i]!=char[i-2],push to "newest stack" 一开始也
就是stack0
如果char[i]=char[i-1]的的时候,偶数palindrome,new queue1, new stack1, char[i]
进去stack1,stack0.pop()进入queue1.
如果char[i]=char[i-2],奇数palindrome,char[i-1],char[i-2]都要从stack0 pop出来
进去queue1, char[i]还是进入stack1
如果stack0空了,是个solution.
在这过程中任何时候stack0+queue1+stack1都可以看成一个整体的stack
一旦又出现char[i]!=char[i-1] &&char[i]!=char[i-2],那么newest stack变成stack1
,循环下去.以后发现可能的palindrome时候要从新到旧把前面的stack和queue都清空才
是solution.
【在 d*******l 的大作中提到】
: 我看过一下，但实在有点复杂一时不能理解啊，就做罢了。我个人感觉上，这个问题很
: 难这么朴素的弄出来，但没有确凿证据我也不敢轻易下结论
|
c********1
发帖数: 161 | 28 我也演算了你的算法，我觉得还有问题啊，比如给个复杂的例子，你的算法怎么work呢
？CASE: ABCDCACDCBA,
在这个例子里面，第一个可能是palindrome的地方发生在(AB）CDC 处， 可是紧接下来
的A不satisfy B，所以按照你的算法，原先的stack1变成new stack，结果，就变成
stack0(top -> bottom):BA, queue1（front -> back）：DC， stack1（new stack
now， top->bottom）:AC
接下来是C， 因为C和stack1中的C(AC中的C)吻合，所以满足char[i] = char[i-2]，接
下来你的算法是“循环下去.以后发现可能的palindrome时候要从新到旧把前面的stack
和queue都清空才是solution”,我实在没弄明白这里是什么意思，接下来要怎么处理？
？？？？？？ |
c********1
发帖数: 161 | 29 这道题困扰了我很久，事实上我觉得就是用好几个stack和queue，这个问题还是很难用
linear time来解决。 |
g*****i
发帖数: 2162 | 30 stack0+queue1+stack1看成一个stack, pop的时候从最后一个stack1开始,最后一个空
了从倒数第二个queue1开始pop(由于是queue,所以实际上是queue的remove()).
stack
【在 c********1 的大作中提到】
: 我也演算了你的算法，我觉得还有问题啊，比如给个复杂的例子，你的算法怎么work呢
: ？CASE: ABCDCACDCBA,
: 在这个例子里面，第一个可能是palindrome的地方发生在(AB）CDC 处， 可是紧接下来
: 的A不satisfy B，所以按照你的算法，原先的stack1变成new stack，结果，就变成
: stack0(top -> bottom):BA, queue1（front -> back）：DC， stack1（new stack
: now， top->bottom）:AC
: 接下来是C， 因为C和stack1中的C(AC中的C)吻合，所以满足char[i] = char[i-2]，接
: 下来你的算法是“循环下去.以后发现可能的palindrome时候要从新到旧把前面的stack
: 和queue都清空才是solution”,我实在没弄明白这里是什么意思，接下来要怎么处理？
: ？？？？？？
|
|
|
d*******l
发帖数: 338 | 31 我也觉得。要在O(n)解决这个问题，要么用强力的数据结构，要么改变算法的本质，总
以为string类的问题要是牵扯上回文，前后缀，不用点nb数据结构是很难用朴素的办法
倒腾出来的。楼上写的很详细但觉得路子有点跑偏了，如果这种问题出现在面试中，应
该是有些切入点的，楼上的方法细节较繁琐，整体路线有点模糊，而且不好证明对也不
好推翻，往往会比较尴尬。
当然如果是纯粹探讨这个解法的可行性也是可以的，不过我等也要写作业实在没法仔细
研究，还是用万能的后缀树吧～
【在 c********1 的大作中提到】
: 这道题困扰了我很久，事实上我觉得就是用好几个stack和queue，这个问题还是很难用
: linear time来解决。
|
r******r
发帖数: 700 | 32 把 longestPrefixPalindrome(String test) 改进了一点，从后面往前面扫描，先找最
大的；如果找到，立即返回。complexity 降到了：
O（n-1/2）* O（n/2）average case.
这还算 O(n^2) 吧？ 再看看 suffix tree.
// ILLINOISURB
public static String longestPrefixPalindrome(String test){
for(int i=test.length()-1; i>=0; i--){
String maxPrefix = test.substring(0, i);
if( isCharPalindrome(maxPrefix) ){
return maxPrefix;
}
}
}
);
-
【在 r******r 的大作中提到】
: 我这个方法很笨。 谁能写个 O(n) 的？ 这个好像也是被 facebook 考了的。
: // civic
: private static boolean isCharPalindrome(String test) {
: String stripped = test.toLowerCase().replaceAll("[^0-9a-zA-Z]", "");
: for(int i = 0; i < stripped.length() / 2; i++) {
: if(stripped.charAt(i) != stripped.charAt(stripped.length() - 1 -
: i)) {
: return false;
: }
: }
|
g*****i
发帖数: 2162 | 33 我写了个程序测试了一下,我的方法有问题.如果有substring是3+个相同的字母,比如aaa,那
么设当前所有stack的状态为K,需要先按照偶数palindrome进行扩展(第三个a是和第二
个a对称),然后回到K,在按照奇数扩展(第三个a和第一个a扩展).要回到原来的状态K可
能就不是O(n)了. 另外如果已经找到了一个palindrome,然后更长的palindrome的起始
点在已经找到的里面,那么也会有问题,要解决就不是O(n)了,有重复扩展.
【在 d*******l 的大作中提到】
: 我也觉得。要在O(n)解决这个问题，要么用强力的数据结构，要么改变算法的本质，总
: 以为string类的问题要是牵扯上回文，前后缀，不用点nb数据结构是很难用朴素的办法
: 倒腾出来的。楼上写的很详细但觉得路子有点跑偏了，如果这种问题出现在面试中，应
: 该是有些切入点的，楼上的方法细节较繁琐，整体路线有点模糊，而且不好证明对也不
: 好推翻，往往会比较尴尬。
: 当然如果是纯粹探讨这个解法的可行性也是可以的，不过我等也要写作业实在没法仔细
: 研究，还是用万能的后缀树吧～
|
r**d
发帖数: 316 | 34 用kmp匹配算法的变形。
同样先算overlap函数，然后从字符尾向头反向匹配。同一般匹配不同的是context结束
就认为成功。第一个匹配 成功的即为所求。
kmp是o(m+n)所以此算法也是o(2n)=o(n)
prefix
S
【在 r******r 的大作中提到】
: 网上看到这个 UIUC 的期末考试题，
: “Describe and analyze an algorithm to find the longest prefix of a given
: string that is also a palindrome. For example, the longest palindrome prefix
: of ILLINOISURBANACHAMPAIGN is ILLI, and the longest palindrome prefix of
: HYAKUGOJYUUICHI is the single letter S.
: For full credit, your algorithm should run in O(n) time.
: ”
: 这个题目中是不是有个笔误，其中 "HYAKUGOJYUUICHI" 的 longes prefix 为什么是 S
: ? 原题在这里：http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/hwex/s01/final.pdf
: 应该是 H 吧？
|
d*******l
发帖数: 338 | 35 这方法有戏。相当于把原串的逆串作为text，原串作为pattern，然后一直匹配到text结束。这时pattern匹配成功的部分就是最长前缀了，直观上应该是正确的
【在 r**d 的大作中提到】
: 用kmp匹配算法的变形。
: 同样先算overlap函数，然后从字符尾向头反向匹配。同一般匹配不同的是context结束
: 就认为成功。第一个匹配 成功的即为所求。
: kmp是o(m+n)所以此算法也是o(2n)=o(n)
:
: prefix
: S
|
