r******l
发帖数: 10760 | 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)的解法，还有没有更好
的解法呢？ |
d*k
发帖数: 207 | 2 说一个思路，适合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)的解法，还有没有更好
: 的解法呢？
|
f*****h
发帖数: 10 | 3 sum[x] = sum[x - 1] + dist(A[x], B[x]) - dist(A[x - k], B[x - k])
time: O(N)
space: O(K) |
r******l
发帖数: 10760 | 4 看不明白。能详细讲讲吗？多谢！
【在 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)
|
f*****h
发帖数: 10 | 5 （如果我没理解错题意的话）
相当于维护一个长度为K的滑动窗口，SUM是这个窗口截取的子串和B的距离。由于距离
的定义是各字符的平方和，窗口向后滑动一位之后，SUM移除了第一个字符的“贡献”
，加入了最后一个字符的“贡献”。
依题意公式里dist(c1, c2) = square(c1 - c2)
【在 r******l 的大作中提到】
: 看不明白。能详细讲讲吗？多谢！
|
D**********d
发帖数: 849 | 6 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); |
a******e
发帖数: 710 | 7 这不太对吧
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)
|
l*n
发帖数: 529 | 8
是字符之差的平方和！
【在 f*****h 的大作中提到】
: （如果我没理解错题意的话）
: 相当于维护一个长度为K的滑动窗口，SUM是这个窗口截取的子串和B的距离。由于距离
: 的定义是各字符的平方和，窗口向后滑动一位之后，SUM移除了第一个字符的“贡献”
: ，加入了最后一个字符的“贡献”。
: 依题意公式里dist(c1, c2) = square(c1 - c2)
|
|
a******e
发帖数: 710 | 9 我想到一个小改进，利用三角不等式，即三角形两边之差<=第三条边的长度
两个字符串看成两个向量: 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 的大作中提到】
: 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)的解法，还有没有更好
: 的解法呢？
|
f*****h
发帖数: 10 | 10 嗯，我搞错了，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）的时间算出新窗口的距离？
|
m******n
发帖数: 187 | 11 听起来像付利叶变换。
如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)的解法，还有没有更好
: 的解法呢？
|
