贴图还是用置顶里面的方法吗？# gardening - 拈花惹草
r*n
1 楼
找到字符串A在字符串B中出现的次数，可以重复使用字母，比如 A: aba B:ababa, 那
么返回2.
只收了O(n*m)的暴力算法，请问最优的，谢谢！
么返回2.
只收了O(n*m)的暴力算法，请问最优的，谢谢！
j*8
2 楼
tks
t*t
3 楼
看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
吗。
吗。
q*y
4 楼
kmp改一点
把A做一个自动机，B在A自动机上过一遍
O(n)
【在 r******n 的大作中提到】
: 找到字符串A在字符串B中出现的次数，可以重复使用字母，比如 A: aba B:ababa, 那
: 么返回2.
: 只收了O(n*m)的暴力算法，请问最优的，谢谢！
把A做一个自动机，B在A自动机上过一遍
O(n)
【在 r******n 的大作中提到】
: 找到字符串A在字符串B中出现的次数，可以重复使用字母，比如 A: aba B:ababa, 那
: 么返回2.
: 只收了O(n*m)的暴力算法，请问最优的，谢谢！
s*o
5 楼
不可以
【在 j*****8 的大作中提到】
: tks
【在 j*****8 的大作中提到】
: tks
G*n
6 楼
是的
【在 t****t 的大作中提到】
: 看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
: 吗。
【在 t****t 的大作中提到】
: 看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
: 吗。
w*x
7 楼
暴力就够了吧
c*y
8 楼
那转到其他amazon账号呢？
u*u
9 楼
我用了个app叫TinyPic,蛮好用的。看版上有人推荐的。
【在 t****t 的大作中提到】
: 看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
: 吗。
【在 t****t 的大作中提到】
: 看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
: 吗。
i*e
10 楼
用DFA的是rabin karp吧？
把KMP改成匹配成功以后如果text string (B) 还没结束，
i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
function对应的位置继续匹配
ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
直到text string 结束，用一个counter记录匹配的次数
【在 q***y 的大作中提到】
: kmp改一点
: 把A做一个自动机，B在A自动机上过一遍
: O(n)
把KMP改成匹配成功以后如果text string (B) 还没结束，
i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
function对应的位置继续匹配
ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
直到text string 结束，用一个counter记录匹配的次数
【在 q***y 的大作中提到】
: kmp改一点
: 把A做一个自动机，B在A自动机上过一遍
: O(n)
c*7
11 楼
no,只能自己账户买东西(不包括买gc)
【在 c*****y 的大作中提到】
: 那转到其他amazon账号呢？
【在 c*****y 的大作中提到】
: 那转到其他amazon账号呢？
y*2
12 楼
就我所知道的常见的有4种方法：
1. flickr.com，我一直在用 ：）
2. TinyPic, 一个免费的app软件，据说很方便。
3. mitbbs手机app，发文的时候加上图片附件。你看到很多的图片文件名
0ImageFromiPhone＊.jpg就是这么贴图的，这个用起来也很方便。
4. 直接从mitbbs.com发帖或回帖的时候加图片附件，缺点是size有限制。
【在 t****t 的大作中提到】
: 看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
: 吗。
1. flickr.com，我一直在用 ：）
2. TinyPic, 一个免费的app软件，据说很方便。
3. mitbbs手机app，发文的时候加上图片附件。你看到很多的图片文件名
0ImageFromiPhone＊.jpg就是这么贴图的，这个用起来也很方便。
4. 直接从mitbbs.com发帖或回帖的时候加图片附件，缺点是size有限制。
【在 t****t 的大作中提到】
: 看到大家的图的链接都不是www.flickr.com里的了。所以问问有什么比较好的方法贴图
: 吗。
q*y
13 楼
rabin karp是什么？
【在 i******e 的大作中提到】
: 用DFA的是rabin karp吧？
: 把KMP改成匹配成功以后如果text string (B) 还没结束，
: i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
: function对应的位置继续匹配
: ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
: 直到text string 结束，用一个counter记录匹配的次数
【在 i******e 的大作中提到】
: 用DFA的是rabin karp吧？
: 把KMP改成匹配成功以后如果text string (B) 还没结束，
: i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
: function对应的位置继续匹配
: ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
: 直到text string 结束，用一个counter记录匹配的次数
g*g
14 楼
想得美
x*6
15 楼
对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
node
的subtree有几个leaf。线性复杂度
node
的subtree有几个leaf。线性复杂度
h*s
16 楼
LZ别想那么多了，Amazon加到账户里的GC只能自己买东西，而且不能买GC。别的什么也
干不了。
【在 c*********7 的大作中提到】
: no,只能自己账户买东西(不包括买gc)
干不了。
【在 c*********7 的大作中提到】
: no,只能自己账户买东西(不包括买gc)
Z*Z
17 楼
写个练手
public static void main(String[] args) {
System.out.println(countOccurrence("gcagagagcagagag", "gcagagag"));
}
public static int countOccurrence(String haystack, String needle){
char[] str = haystack.toCharArray();
char[] pattern = (needle + '\0').toCharArray();
int n = needle.length();
int[] table = buildFailureTable(pattern);
int count = 0;
int i = 0, j = 0;
while(i < str.length){
while(j > 0 && pattern[j] != str[i]){
j = table[j];
}
i ++;
j ++;
if(j == n){
count ++;
j = table[j];
}
}
return count;
}
private static int[] buildFailureTable(char[] pattern) {
int[] arr = new int[pattern.length];
int i = 0;
int j = -1;
arr[0] = -1;
while(i < arr.length - 1){
while(j >= 0 && pattern[i] != pattern[j]){
j = arr[j];
}
i++;
j++;
if(pattern[i] == pattern[j]){
arr[i] = arr[j];
} else {
arr[i] = j;
}
}
return arr;
}
【在 i******e 的大作中提到】
: 用DFA的是rabin karp吧？
: 把KMP改成匹配成功以后如果text string (B) 还没结束，
: i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
: function对应的位置继续匹配
: ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
: 直到text string 结束，用一个counter记录匹配的次数
public static void main(String[] args) {
System.out.println(countOccurrence("gcagagagcagagag", "gcagagag"));
}
public static int countOccurrence(String haystack, String needle){
char[] str = haystack.toCharArray();
char[] pattern = (needle + '\0').toCharArray();
int n = needle.length();
int[] table = buildFailureTable(pattern);
int count = 0;
int i = 0, j = 0;
while(i < str.length){
while(j > 0 && pattern[j] != str[i]){
j = table[j];
}
i ++;
j ++;
if(j == n){
count ++;
j = table[j];
}
}
return count;
}
private static int[] buildFailureTable(char[] pattern) {
int[] arr = new int[pattern.length];
int i = 0;
int j = -1;
arr[0] = -1;
while(i < arr.length - 1){
while(j >= 0 && pattern[i] != pattern[j]){
j = arr[j];
}
i++;
j++;
if(pattern[i] == pattern[j]){
arr[i] = arr[j];
} else {
arr[i] = j;
}
}
return arr;
}
【在 i******e 的大作中提到】
: 用DFA的是rabin karp吧？
: 把KMP改成匹配成功以后如果text string (B) 还没结束，
: i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
: function对应的位置继续匹配
: ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
: 直到text string 结束，用一个counter记录匹配的次数
i*e
18 楼
见CLRS 3rd Edition pp.990-995
【在 q***y 的大作中提到】
: rabin karp是什么？
【在 q***y 的大作中提到】
: rabin karp是什么？
h*8
19 楼
正准备换工作，请教大牛们，我也研究生CS，没学过这末复杂的算法，你们都是自学的
？我看了下CLRS，天书一样,一下泄气了大半。
【在 i******e 的大作中提到】
: 见CLRS 3rd Edition pp.990-995
？我看了下CLRS，天书一样,一下泄气了大半。
【在 i******e 的大作中提到】
: 见CLRS 3rd Edition pp.990-995
f*h
20 楼
但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。
【在 x*******6 的大作中提到】
: 对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
: node
: 的subtree有几个leaf。线性复杂度
【在 x*******6 的大作中提到】
: 对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
: node
: 的subtree有几个leaf。线性复杂度
g*e
21 楼
O(n)
http://pdf.aminer.org/000/979/588/space_efficient_linear_time_c
【在 f******h 的大作中提到】
: 但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。
http://pdf.aminer.org/000/979/588/space_efficient_linear_time_c
【在 f******h 的大作中提到】
: 但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。
相关阅读