【转让】CVS$25不跟卡转处方coupon+bonus - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

【转让】CVS$25不跟卡转处方coupon+bonus

【转让】CVS$25不跟卡转处方coupon+bonus# PennySaver - 省钱一族

r*l2010-08-06 07:08

1 楼

strstr的一个变种。输入是两个string A和B，长度分别是n和k（n>>k）。输出是A里面
的一个长度为k的substr C，要求B和C之间的距离最小。两个等长的string的距离的定
义为每个对应字符之间距离的平方之和。两个字符之间的距离就是ASCII码的差（比如A
和B的距离为1，A和Z的距离为25）。
如果B是A的子串，则C=B，最小距离就是0。这个可以用KMP、BM、RK等很多方法快速解
决。但是如果B不一定是A的子串，除了最直接的双重循环O(nk)的解法，还有没有更好
的解法呢？

l*y2010-08-06 07:08

2 楼

不建议交易打印胖子；胖子是免费的，收费的是服务:
所卖物品名称:
CVS $25 新处方胖子
物品类别（coupon: mfc 等；血糖仪等）:
Coupons，不跟卡
物品来源（报纸夹页，厂家邮寄等）:
邮寄到家
可接受的价格（必须明码标价，必填）:
$4/张（包邮费）
$8/两张+bonus cvs 5 off 30 coupon （8/21/10 expires）
邮寄损失方式哪方承担（若需邮寄，必填）:
default
付款方式说明:
paypal
本贴有效期（必填）:
till sold
联系方式（例：站内）:
站内

d*k2010-08-06 07:08

3 楼

说一个思路，适合k很小或者char的取值范围很小时候。预处理把所有长度为k的string
和B的距离算出来放到hash table里面。顺序扫描一遍A，对于每个遇到的字串，在hash
table里直接获得它和B的距离。
普通的hash table算一个字串的hash需要O(k)的时间，这样总体和暴力解法一样。因此
需要自己设计hash。很多rolling hash（http://en.wikipedia.org/wiki/Rolling_hash）都可以满足。这样计算第一个字串的hash需要O(k)的时间，后面每一个只需O（1）的时间。
若char的取值个数是O(v)，则预处理时间是O(v^k），之后扫描的时间是O(n)。

如A

【在 r******l 的大作中提到】

: strstr的一个变种。输入是两个string A和B，长度分别是n和k（n>>k）。输出是A里面
: 的一个长度为k的substr C，要求B和C之间的距离最小。两个等长的string的距离的定
: 义为每个对应字符之间距离的平方之和。两个字符之间的距离就是ASCII码的差（比如A
: 和B的距离为1，A和Z的距离为25）。
: 如果B是A的子串，则C=B，最小距离就是0。这个可以用KMP、BM、RK等很多方法快速解
: 决。但是如果B不一定是A的子串，除了最直接的双重循环O(nk)的解法，还有没有更好
: 的解法呢？

a*n2010-08-06 07:08

4 楼

我晕，这个胖胖那么值钱？。。。

【在 l*******y 的大作中提到】

: 不建议交易打印胖子；胖子是免费的，收费的是服务:
: 所卖物品名称:
: CVS $25 新处方胖子
: 物品类别（coupon: mfc 等；血糖仪等）:
: Coupons，不跟卡
: 物品来源（报纸夹页，厂家邮寄等）:
: 邮寄到家
: 可接受的价格（必须明码标价，必填）:
: $4/张（包邮费）
: $8/两张+bonus cvs 5 off 30 coupon （8/21/10 expires）

f*h2010-08-06 07:08

5 楼

sum[x] = sum[x - 1] + dist(A[x], B[x]) - dist(A[x - k], B[x - k])
time: O(N)
space: O(K)

l*y2010-08-06 07:08

6 楼

我看大家都是这个价转的。。。而且ebay上面好像更贵。。。

【在 a******n 的大作中提到】

: 我晕，这个胖胖那么值钱？。。。

r*l2010-08-06 07:08

7 楼

看不明白。能详细讲讲吗？多谢！

【在 f*****h 的大作中提到】

: sum[x] = sum[x - 1] + dist(A[x], B[x]) - dist(A[x - k], B[x - k])
: time: O(N)
: space: O(K)

i*y2010-08-06 07:08

8 楼

这个价钱都被新手们抬成这样了，我以前都是$1的求到的
现在这么贵不划算，几个pharmacy免费转转药算了

【在 a******n 的大作中提到】

: 我晕，这个胖胖那么值钱？。。。

f*h2010-08-06 07:08

9 楼

（如果我没理解错题意的话）
相当于维护一个长度为K的滑动窗口，SUM是这个窗口截取的子串和B的距离。由于距离
的定义是各字符的平方和，窗口向后滑动一位之后，SUM移除了第一个字符的“贡献”
，加入了最后一个字符的“贡献”。
依题意公式里dist(c1, c2) = square(c1 - c2)

【在 r******l 的大作中提到】

: 看不明白。能详细讲讲吗？多谢！

l*y2010-08-06 07:08

10 楼

偶新来的，就是跟风标价：）
已经根据大家的建议降价了～

【在 i****y 的大作中提到】

: 这个价钱都被新手们抬成这样了，我以前都是$1的求到的
: 现在这么贵不划算，几个pharmacy免费转转药算了

D*d2010-08-06 07:08

11 楼

time: O(N) just need to scan A for one time
space: O(1), maintain two sums:
s1(i): sum of squares up to i;
s2(i): sum of squres up to i-k.
Then the distance between A[i-k+1:i] and B is d(i) := s1(i)-s2(i);

l*y2010-08-06 07:08

12 楼

又降价了：）

a*e2010-08-06 07:08

13 楼

这不太对吧
strA = "ABCD"
strB = "EFG"
那么最开始的窗口，平方和为 (A-E)^2 + (B-F)^2 + (C-G)^2
窗口滑动一位之后，平方和为 (B-E)^2 + (C-F)^2 + (D-G)^2
好像没法用O（1）的时间算出新窗口的距离？

【在 f*****h 的大作中提到】

: （如果我没理解错题意的话）
: 相当于维护一个长度为K的滑动窗口，SUM是这个窗口截取的子串和B的距离。由于距离
: 的定义是各字符的平方和，窗口向后滑动一位之后，SUM移除了第一个字符的“贡献”
: ，加入了最后一个字符的“贡献”。
: 依题意公式里dist(c1, c2) = square(c1 - c2)

q*u2010-08-06 07:08

14 楼

l*n2010-08-06 07:08

15 楼

是字符之差的平方和！

【在 f*****h 的大作中提到】

q*u2010-08-06 07:08

16 楼

a*e2010-08-06 07:08

17 楼

我想到一个小改进，利用三角不等式，即三角形两边之差<=第三条边的长度
两个字符串看成两个向量: B 和 C， C是A的子串。
现在要找距离B最小的C。
我们设三角形的第三点为原点O，这样d(B,O)的距离就固定了，d(C,O)的距离可以在O(
1)时间内得到，因为d(C,O)就是各个字符的平方和。
根据三角不等式，我们有
d(B,C)>= abs( d(B,O) - d(C,O) )
其中右半部分部分可以在O(1)时间内得到。如果算出来的这个d(B,C)的下限比目前的
最小距离还大，那么这个C显然不可能是最近的子串，就不用再去计算d(B,C)了。
此思路与rolling hash有相似之处，只不过效率稍逊rolling hash，因为好的hash
function可以大幅减少collision

如A

【在 r******l 的大作中提到】

q*u2010-08-06 07:08

18 楼

I want them.

f*h2010-08-06 07:08

19 楼

嗯，我搞错了，dek给的答案很全面

【在 a******e 的大作中提到】

: 这不太对吧
: strA = "ABCD"
: strB = "EFG"
: 那么最开始的窗口，平方和为 (A-E)^2 + (B-F)^2 + (C-G)^2
: 窗口滑动一位之后，平方和为 (B-E)^2 + (C-F)^2 + (D-G)^2
: 好像没法用O（1）的时间算出新窗口的距离？