a**d
发帖数: 85 | 1 You are getting a stream of characters and at any time you can be asked to
find out if the string received yet is palindrome or not.
There can be multiple queries. O(n) and No extra space.
在careercup上看到的。
int val=0,每次有一个新的char进来，就val ^ new char.
query时候就看val是否为0.
如果query是在读完第一个char之后，那就return true。
大家觉得这样对不？ |
s*w
发帖数: 729 | 2 显然不对啊；
aabb 不是 palindrome 但是 xor 起来等于０
aba 是，但是 xor 不等于０
【在 a**d 的大作中提到】
: You are getting a stream of characters and at any time you can be asked to
: find out if the string received yet is palindrome or not.
: There can be multiple queries. O(n) and No extra space.
: 在careercup上看到的。
: int val=0,每次有一个新的char进来，就val ^ new char.
: query时候就看val是否为0.
: 如果query是在读完第一个char之后，那就return true。
: 大家觉得这样对不？
|
a**d
发帖数: 85 | 3 lol
2b了。。。
大神有何想法？
【在 s*w 的大作中提到】
: 显然不对啊；
: aabb 不是 palindrome 但是 xor 起来等于０
: aba 是，但是 xor 不等于０
|
s*w
发帖数: 729 | 4 每个大神都是从２b 过来的
２b, 3b, 4b, ... NB
我不是大神，没解。
觉得可以用 rolling hash, 不过还是解不好。 要是能有一个左边的 rolling hash,
一个右边的 rolling hash, 就只需要update 他们，查看是否相等；关键是搞不清楚
怎么更新这个中间的 char。如果这个 stream 能存下来，就没问题了；不过既然是
stream, 那就是说太大了不让存的。
【在 a**d 的大作中提到】
: lol
: 2b了。。。
: 大神有何想法？
|
e*******n
发帖数: 23 | 5 set 2 pointer. 1st pointer move 1 char each time. 2nd pointer move 2 char
each time. when the 2nd pointer reach the end, the 1 st pointer is in the
middle of stream. then now set 2 pointers in this middle. 1 pointer go left
each time and another one go right and check if these 2 pointer always point
to same char. |
