算法问题求教：字符串比较 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

算法问题求教：字符串比较

算法问题求教：字符串比较# Programming - 葵花宝典

l*d2008-06-12 07:06

1 楼

【以下文字转载自 Immigration 讨论区】
发信人: ladyred (落红万点，好运名：小旺红), 信区: Immigration
标题: Re: [包子贴] LD的J1 waiver下来前能和我一起递I-485吗
发信站: BBS 未名空间站 (Sat Dec 10 22:13:58 2011, 美东)
两人一起递485吧，如果有rfe就答rfe好了。
您递交了485后，您LD也是可以递485的。您说的“她将失去了递485的机会”不大准确。
waiver
12

m*n2008-06-12 07:06

2 楼

http://www.youtube.com/watch?v=4_ibGXbqg3A&feature=related

d*82008-06-12 07:06

3 楼

【以下文字转载自 Piebridge 讨论区】
发信人: CrazyGrape (一块砖头走鹊桥), 信区: Piebridge
标题: Re: 大家说说看怎么找best match？大家都来关心下橙子。
发信站: BBS 未名空间站 (Wed Dec 23 02:56:40 2009, 美东)
我首先自己来说说，我一般会喜欢什么样的女生吧。
大家都看看我的签名就知道了。
我觉得女生不必太漂亮，相对于我自己而言，我对自己没什么自信，我觉得一般的就
可以了。你也许会鄙视我，但我的观点真的就是这样的。长的好看固然更好，但是
漂亮的女朋友并不代表会是一个好老婆。
女生性格要好，不要太强势，有时候要适当在男生面前示弱一下，这样会让男生觉
得你更加值得呵护。
说到这里，对于那些欠砖头砸的人，我要澄清一点，我这里说的适当的示弱，跟大
男子主义没关系，所以不要过来接砖头。
我说的就是大部分男生就是这么想的，你可以跟我辩论这一点，但是即使你辩赢了
又有什么意义呢？
我只是说男生心里就是这么想的，辩论赢了也只是驳倒我这个帖子，你不能改变男
生怎么想的。

m*s2008-06-12 07:06

4 楼

给两个字符串数组，不考虑顺序的情况下，判断是否相同。
例子：
1. Input {"abc", "bcd"} {"bcd", "abc"} Output true
2. Input {"abf", "bcd"} {"abh", "bcd"} Output false
除了枚举法，有无其他更好的方法？
多谢

F*n2008-06-12 07:06

5 楼

You can submit 485 once the DOS sends favorable recommendation (FR) to USCIS
. You can send final approval notice of J1 waiver later. Just include a copy
of the FR in the 485 package.
However, if you don't have FR, you cannot submit 485. Your application will
be rejected even if you send them a waiver which is dated later than your
application date.

确。

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

: 【以下文字转载自 Immigration 讨论区】
: 发信人: ladyred (落红万点，好运名：小旺红), 信区: Immigration
: 标题: Re: [包子贴] LD的J1 waiver下来前能和我一起递I-485吗
: 发信站: BBS 未名空间站 (Sat Dec 10 22:13:58 2011, 美东)
: 两人一起递485吧，如果有rfe就答rfe好了。
: 您递交了485后，您LD也是可以递485的。您说的“她将失去了递485的机会”不大准确。
: waiver
: 12

o*o2008-06-12 07:06

6 楼

hash

【在 m******s 的大作中提到】

: 给两个字符串数组，不考虑顺序的情况下，判断是否相同。
: 例子：
: 1. Input {"abc", "bcd"} {"bcd", "abc"} Output true
: 2. Input {"abf", "bcd"} {"abh", "bcd"} Output false
: 除了枚举法，有无其他更好的方法？
: 多谢

l*d2008-06-12 07:06

7 楼

多谢答复！已转发给原发帖人～

USCIS
copy
will

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

: You can submit 485 once the DOS sends favorable recommendation (FR) to USCIS
: . You can send final approval notice of J1 waiver later. Just include a copy
: of the FR in the 485 package.
: However, if you don't have FR, you cannot submit 485. Your application will
: be rejected even if you send them a waiver which is dated later than your
: application date.
:
: 确。

s*e2008-06-12 07:06

8 楼

先排序后比较。比较两个字符串的大小，可以有多种方法。O(NLogN)

【在 m******s 的大作中提到】

f*Q2008-06-12 07:06

9 楼

俺记着有人研究过说数量少的话枚举核算，过了一定数量hash核算。

l*82008-06-12 07:06

10 楼

calculate MD5 for every string, sort the MD5, then compare

b*e2008-06-12 07:06

11 楼

Use suffix tree.
Build a suffix tree from list a, and then match it against list b.
This is a linear algorithm.

l*82008-06-12 07:06

12 楼

This seems to be checking whether b is a subset of a?

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

: Use suffix tree.
: Build a suffix tree from list a, and then match it against list b.
: This is a linear algorithm.

w*b2008-06-12 07:06

13 楼

I feel sorting each arrays and then comparing it is the best way to do it.

【在 m******s 的大作中提到】

l*82008-06-12 07:06

14 楼

Yes; but the point of MD5 (or other "secure" hash functions with long
outputs) is to reduce string length and allow constant-time comparison,
hence faster sorting.

w*h2008-06-12 07:06

15 楼

hash不能保证最后答案一定正确吧
不同的字符串得到同一个hash值怎么办？

g*r2008-06-12 07:06

16 楼

For the first array, map[string]++, for the second array, map[string]--.
Check if all map[string] == 0 at the end.

f*62008-06-12 07:06

17 楼

The problem doesn't say the array is a set, i.e., there may be duplicates in
the same array.

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

: For the first array, map[string]++, for the second array, map[string]--.
: Check if all map[string] == 0 at the end.

l*82008-06-12 07:06

18 楼

Yes there will be hash collisions, but you can always choose a sufficiently
long hash function (like SHA-512) to diminish the likelihood.

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

: hash不能保证最后答案一定正确吧
: 不同的字符串得到同一个hash值怎么办？

p*g2008-06-12 07:06

19 楼

假设字符串没有重复的字符
compare[a...b] = {0, 0, ...}
if(strlen(input1)!=strlen(input2)) return false;
for(p=input1;pcompare[*p]=1;
for(p=input2;pif(!compare[*p])
return false;
return true

l*d2008-06-12 07:06

20 楼

duplicates doesn't influence the results IMO, say 1st:{"abc","abc"}, then
map("abc")=2, 2nd {"abc","abc"} then map("abc")=0;

in

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

: The problem doesn't say the array is a set, i.e., there may be duplicates in
: the same array.