w****x
发帖数: 2483 | 1 在一个大串中查找和另外一个字符串是anagram的子串:
GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
就是两个指针一前一后, 但是每次查找都要检查rec[256], 时间复杂度是256*O(n), 其
实还不如nlogn. 有其他简单的办法吗?? | f*******t
发帖数: 7549 | 2 这是sliding window的变种吧，用两个hashtable，O(n+m)时间内可解决 | c****p
发帖数: 6474 | 3 hash一下不就行了么。。
滑动窗口，每滑动一次O1的代价。
hash不同就跳过，相同的话验证下是不是真的是anagram。
【在 w****x 的大作中提到】
: 在一个大串中查找和另外一个字符串是anagram的子串:
: GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
: 就是两个指针一前一后, 但是每次查找都要检查rec[256], 时间复杂度是256*O(n), 其
: 实还不如nlogn. 有其他简单的办法吗??
| w****x
发帖数: 2483 | 4
你怎么个hash法? 你每次滑动的时候hash要重新算一遍?
【在 c****p 的大作中提到】
: hash一下不就行了么。。
: 滑动窗口，每滑动一次O1的代价。
: hash不同就跳过，相同的话验证下是不是真的是anagram。
| w****x
发帖数: 2483 | | A*H
发帖数: 127 | 6 you can use rolling hash
【在 w****x 的大作中提到】
: 哦, 你指XOR那种局部计算的hash?
| c****p
发帖数: 6474 | 7 最简单的hash就可以了，比如把window内部的字节xor到一起。
滑动后把当前的hash值分别和滑出的字符和滑入的字符xor一下就是新的hash值，
代价O1。【 在 wwwyhx (wwwyhx) 的大作中提到: 】 | w****x
发帖数: 2483 | | D********g
发帖数: 650 | 9 用HashTable存target的anagram, e.g., {s->1, c->2, d->1, b->1}。
然后用一个同等长度的window在source里平移，对每个字符，如果不在HT里，则非
anagram，否则对应字符freq --，如果freq < 0，则非；如果整个window走完，则是
anagram。
O(n)
【在 w****x 的大作中提到】
: 在一个大串中查找和另外一个字符串是anagram的子串:
: GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
: 就是两个指针一前一后, 但是每次查找都要检查rec[256], 时间复杂度是256*O(n), 其
: 实还不如nlogn. 有其他简单的办法吗??
| s*******f
发帖数: 1114 | 10 This is O(n). Hard to explain, but i think it deserve to go through it with
your test case.
//zzzz码遍本版，回报本版zzzz
//在一个大串中查找和另外一个字符串是anagram的子串:
//GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
string GetAnagram(const char *s, const char *sub){
int ls = strlen(s);
int lsub = strlen(sub);
if (ls < lsub || lsub < 1)
return "";
int mp[256];
memset(mp, 0, 256 * sizeof(int));
while (*sub){
++mp[*sub++];
}
const char *p = s;
int count = 0;
while (*p){
if (mp[*p] <= 0){ //no such character
//recover map
while (s < p){
if (*s == *p) //slice window.
break;
++mp[*s++];
--count;
}
++s;
} else {
--mp[*p];
if (++count >= lsub){
return string(s, p + 1);
}
}
++p;
}
return "";
}
void TestGetAnagram(){
string a = GetAnagram("abcdbcsdaqdbahs", "scdcb");
string b = GetAnagram("abcdbcsdaqdbahs", "a");
string c = GetAnagram("abcdbcsdaqdbahs", "ab");
string d = GetAnagram("abcdbcsdaqdbahs", "ba");
string e = GetAnagram("abcdbcsdaqdbahs", "cdbbcasdqdahabs");
string f = GetAnagram("abcdbcsdaqdbahs", "cdbzhs");
}
【在 w****x 的大作中提到】
: 在一个大串中查找和另外一个字符串是anagram的子串:
: GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
: 就是两个指针一前一后, 但是每次查找都要检查rec[256], 时间复杂度是256*O(n), 其
: 实还不如nlogn. 有其他简单的办法吗??
| p****a
发帖数: 447 | 11 不是吧,恢复map还一个while呢
with
【在 s*******f 的大作中提到】
: This is O(n). Hard to explain, but i think it deserve to go through it with
: your test case.
: //zzzz码遍本版，回报本版zzzz
: //在一个大串中查找和另外一个字符串是anagram的子串:
: //GetAnagram("abcdbcsdaqdbahs", "scdcb") ==> "cdbcs"
: string GetAnagram(const char *s, const char *sub){
: int ls = strlen(s);
: int lsub = strlen(sub);
: if (ls < lsub || lsub < 1)
: return "";
|
|
