a**m
发帖数: 151 | 1 1. you are given two arrays. A of size n, B of size m. m is a very very
small number compared to n. find out if A contains a substring which is
anagram of B.
有O(m+n)的算法吗？
2. 很类似的题，找A里最小window包含B中的所有元素而且顺序相同。
thanks. |
g***s
发帖数: 3811 | 2 it was discussed a few months ago
【在 a**m 的大作中提到】
: 1. you are given two arrays. A of size n, B of size m. m is a very very
: small number compared to n. find out if A contains a substring which is
: anagram of B.
: 有O(m+n)的算法吗？
: 2. 很类似的题，找A里最小window包含B中的所有元素而且顺序相同。
: thanks.
|
r******l
发帖数: 10760 | 3 更否给个思路，或者link？
【在 g***s 的大作中提到】
: it was discussed a few months ago
|
s*****n
发帖数: 5488 | 4 1.建立b的hashtable.
扫描A,如果m项都match, return true;
如果某字符 a match多1，remove all matches before the first a's position.
如果出现了字符不在hashtable, remove all matches
如果match，则记录下位置
should be o(m+n)
【在 a**m 的大作中提到】
: 1. you are given two arrays. A of size n, B of size m. m is a very very
: small number compared to n. find out if A contains a substring which is
: anagram of B.
: 有O(m+n)的算法吗？
: 2. 很类似的题，找A里最小window包含B中的所有元素而且顺序相同。
: thanks.
|
s*****y
发帖数: 897 | 5 什么是如果某字符 a match多1？
Thanks |
s*****n
发帖数: 5488 | 6 假设
A: abaac
B: abc
则 在第三个iteration,出现了第二个a,而B应该只有一个a,那么应该从A[2] = b开始重
新进行match. |
g**e
发帖数: 6127 | 7 扫一遍B得到一个signature，然后开一个m大小的window沿着A扫描，每次移动一个字符
更新window内字符串的signature，如果跟B一样就返回true
【在 s*****n 的大作中提到】
: 1.建立b的hashtable.
: 扫描A,如果m项都match, return true;
: 如果某字符 a match多1，remove all matches before the first a's position.
: 如果出现了字符不在hashtable, remove all matches
: 如果match，则记录下位置
: should be o(m+n)
|
a**m
发帖数: 151 | |
f****4
发帖数: 1359 | 9 clrs 2rd, 32.2
或者直接wiki Rabin-Karp algorithm
【在 a**m 的大作中提到】
: 什么是signature?
|
r******l
发帖数: 10760 | 10 你这个假设B没有重复字母吗？原题没有这种假设吧？
【在 s*****n 的大作中提到】
: 假设
: A: abaac
: B: abc
: 则 在第三个iteration,出现了第二个a,而B应该只有一个a,那么应该从A[2] = b开始重
: 新进行match.
|
|
|
a**m
发帖数: 151 | 11
Thanks. 那第二题怎么做？
【在 f****4 的大作中提到】
: clrs 2rd, 32.2
: 或者直接wiki Rabin-Karp algorithm
|
x******2
发帖数: 546 | 12 DP？
S(a,b)表示恰用了A[a]到A[b]中最长所含有的B的长度，且必须满足A[a]=B[1],A[b]为
该最长字串的最后一个字符。
则S(a,b)=min(k=a...b-1){ S(a,k)+1 | A[b]=B[S[a,b-1]+1] }
最后答案应该在所有的S(a,b)对中找出满足S(a,b)=m且b-a+1最小的那个。
这个复杂度是O(N^3)，不知道有没有更好的
【在 a**m 的大作中提到】
:
: Thanks. 那第二题怎么做？
|
A***M
发帖数: 18 | 13 太复杂了啊
其实就是一个变形的KMP吧
【在 x******2 的大作中提到】
: DP？
: S(a,b)表示恰用了A[a]到A[b]中最长所含有的B的长度，且必须满足A[a]=B[1],A[b]为
: 该最长字串的最后一个字符。
: 则S(a,b)=min(k=a...b-1){ S(a,k)+1 | A[b]=B[S[a,b-1]+1] }
: 最后答案应该在所有的S(a,b)对中找出满足S(a,b)=m且b-a+1最小的那个。
: 这个复杂度是O(N^3)，不知道有没有更好的
|
x******2
发帖数: 546 | 14 没发现怎么用KMP搞，
求具体
【在 A***M 的大作中提到】
: 太复杂了啊
: 其实就是一个变形的KMP吧
|
q****x
发帖数: 7404 | 15 how to handle anagram condition?
【在 f****4 的大作中提到】
: clrs 2rd, 32.2
: 或者直接wiki Rabin-Karp algorithm
|
g**e
发帖数: 6127 | 16 我开始也以为KMP变一下可以，仔细想了一下似乎不行
【在 x******2 的大作中提到】
: 没发现怎么用KMP搞，
: 求具体
|
x******2
发帖数: 546 | 17 是啊，我觉得只能DP搞第二题的
【在 g**e 的大作中提到】
: 我开始也以为KMP变一下可以，仔细想了一下似乎不行
|
s*****y
发帖数: 897 | 18 第2题
可否这样子：
1. 扫描B，建hashtable，同时建KMP的东西
2. 扫描A，如果出现不在Hashtable的字符，就删除这个字符，然后把删除的字符数目
存在上一个在B里面出现的字符里面。
3. KMP搜索压缩后的A，找到所有match的string，计算长度，长度=B的长度+每个match的字符对
应的后面删除的字符数目。update一个全局的最小长度。
例子，adbezcgfiacbdcabc 找a b c
压缩A成为 a1b2c3a0c0b0a0b0c0 每个数字代表后面删除的字符数量.数字单独存在一个
数组里面
然后KMP搜索abcacbabc，第一个abcmatch 得到长度6
最后一个abc match，得到长度3。 |
f*********1
发帖数: 75 | 19 第2题是不是两个string 找 longest subsequence啊？
【在 a**m 的大作中提到】
: 1. you are given two arrays. A of size n, B of size m. m is a very very
: small number compared to n. find out if A contains a substring which is
: anagram of B.
: 有O(m+n)的算法吗？
: 2. 很类似的题，找A里最小window包含B中的所有元素而且顺序相同。
: thanks.
|
x******2
发帖数: 546 | 20 我觉得LZ的第二题的题目里的substring是指可以跳跃的字串，而kmp解决的必须是连续
的字串。
你的方法不能handle字符跳跃的问题
match的字符对
【在 s*****y 的大作中提到】
: 第2题
: 可否这样子：
: 1. 扫描B，建hashtable，同时建KMP的东西
: 2. 扫描A，如果出现不在Hashtable的字符，就删除这个字符，然后把删除的字符数目
: 存在上一个在B里面出现的字符里面。
: 3. KMP搜索压缩后的A，找到所有match的string，计算长度，长度=B的长度+每个match的字符对
: 应的后面删除的字符数目。update一个全局的最小长度。
: 例子，adbezcgfiacbdcabc 找a b c
: 压缩A成为 a1b2c3a0c0b0a0b0c0 每个数字代表后面删除的字符数量.数字单独存在一个
: 数组里面
|
|
|
f*******t
发帖数: 7549 | 21 第一题的解法：
1.先对B建立一个hashtable，统计每个字母出现的次数，复杂度O(m)。
2.从i=0开始扫描A[i]，每读入一个A[i]查看B的hashtable里对应的次数是不是大于0，
如果是则次数减掉1，并且i++，x++。（记录当前已经完成匹配的字符串长度为x，当前
字符index为i)
3.如果读入的字符在hashtable里的次数等于0，说明以前读过的字符串肯定不是
anagram。于是从A[i-x]开始丢弃（x--），每丢弃一个字符对应的hashtable里次数加1
，直到丢弃的A[i-x]与A[i]是相同的——这时重新开始i++。
4.当x==m时说明找到了相应的子串。
最坏情况下B被扫描两遍，所以总的复杂度是O(n+m)。 |
f*******t
发帖数: 7549 | 22 第二题的解法：
当然用DP来做。
int minWindow(A[1...n], B[1...m])
{
//B为空串，说明已经匹配完成
if(m == 0)
return 0
//A已经成为空串而B里仍有字符，说明此路不通
if(n == 0)
return INFINITY
if(A[n] == B[m])
return MIN(minWindow(A[1...n-1], B[1...m-1]) + 1, minWindow(A[1...n-1],
B[1...m]) //DP
else
return minWindow(A[1...n-1], B[1...m]) //继续找
}
这样得到的是最小的窗口大小，但题目似乎要求找到确切的i、j值，所以稍微改一下返回的值为当前最大的n值就可以了 |
q****x
发帖数: 7404 | 23 没看懂。说说解法？
【在 f*******t 的大作中提到】
: 第二题的解法：
: 当然用DP来做。
: int minWindow(A[1...n], B[1...m])
: {
: //B为空串，说明已经匹配完成
: if(m == 0)
: return 0
: //A已经成为空串而B里仍有字符，说明此路不通
: if(n == 0)
: return INFINITY
|
q****x
发帖数: 7404 | 24 还是没看懂。但直觉上觉得有问题。
加1
【在 f*******t 的大作中提到】
: 第一题的解法：
: 1.先对B建立一个hashtable，统计每个字母出现的次数，复杂度O(m)。
: 2.从i=0开始扫描A[i]，每读入一个A[i]查看B的hashtable里对应的次数是不是大于0，
: 如果是则次数减掉1，并且i++，x++。（记录当前已经完成匹配的字符串长度为x，当前
: 字符index为i)
: 3.如果读入的字符在hashtable里的次数等于0，说明以前读过的字符串肯定不是
: anagram。于是从A[i-x]开始丢弃（x--），每丢弃一个字符对应的hashtable里次数加1
: ，直到丢弃的A[i-x]与A[i]是相同的——这时重新开始i++。
: 4.当x==m时说明找到了相应的子串。
: 最坏情况下B被扫描两遍，所以总的复杂度是O(n+m)。
|
q****x
发帖数: 7404 | 25 太花哨。十有八九不对。
match的字符对
【在 s*****y 的大作中提到】
: 第2题
: 可否这样子：
: 1. 扫描B，建hashtable，同时建KMP的东西
: 2. 扫描A，如果出现不在Hashtable的字符，就删除这个字符，然后把删除的字符数目
: 存在上一个在B里面出现的字符里面。
: 3. KMP搜索压缩后的A，找到所有match的string，计算长度，长度=B的长度+每个match的字符对
: 应的后面删除的字符数目。update一个全局的最小长度。
: 例子，adbezcgfiacbdcabc 找a b c
: 压缩A成为 a1b2c3a0c0b0a0b0c0 每个数字代表后面删除的字符数量.数字单独存在一个
: 数组里面
|
s*****y
发帖数: 897 | 26 can you give me a counter example?
I wil try to code it using this method.
【在 q****x 的大作中提到】
: 太花哨。十有八九不对。
:
: match的字符对
|
m**q
发帖数: 189 | 27 每次直接计算signature我觉得需要O(m),因为我们需要anagram所以
无法像RK算法那样增量计算，最终的复杂度应该是O(mn)
（n为字符串a的长度，m为b的长度）
我想到的一个改进是：
1） 用一个数组统计b中每个字符出现的次数，如果字符串只包含
a~z，长度为26的数组就够了，设此数组为limit[]
2） 用一个长度为m的窗口扫描a，用一个长为26的数组cnt[]统计
每个字符在窗口中出现的次数（只统计在b中出现的字符），另外
维护一个counter，
在把字符c加入窗口时，cnt[c]++, 如果cnt[c] <= limit[c]则递增counter；
在把字符c从窗口中拿走时，cnt[c]--,如果cnt[c] < limit[c]则递减counter，
当counter==m的时候则找到b的anagram。
这里counter的使用，使得每次判断anagram可以用O(1)实现，
于是整个算法可以用O(m+n)完成。
这里借鉴了 darksteel 在计算最小包含窗口那个经典题的思路。
【在 g**e 的大作中提到】
: 扫一遍B得到一个signature，然后开一个m大小的window沿着A扫描，每次移动一个字符
: 更新window内字符串的signature，如果跟B一样就返回true
|
m**q
发帖数: 189 | 28 这个好像是公共子序列吧，不能保证一定能找到最短的window啊
【在 f*******t 的大作中提到】
: 第二题的解法：
: 当然用DP来做。
: int minWindow(A[1...n], B[1...m])
: {
: //B为空串，说明已经匹配完成
: if(m == 0)
: return 0
: //A已经成为空串而B里仍有字符，说明此路不通
: if(n == 0)
: return INFINITY
|
m**q
发帖数: 189 | 29 第二题我的思路：
扫描一遍A，对于B中包含的每个字符，记录它在A中出现的所有位置。
然后从后向前扫描这些位置序列，总的复杂度应该不超过O(mn)，
记得以前看过这题但忘了最优解是什么了。。。
【在 a**m 的大作中提到】
: 1. you are given two arrays. A of size n, B of size m. m is a very very
: small number compared to n. find out if A contains a substring which is
: anagram of B.
: 有O(m+n)的算法吗？
: 2. 很类似的题，找A里最小window包含B中的所有元素而且顺序相同。
: thanks.
|
