标题：今天很有收获
出处：Felix021
时间：Sun, 07 Jun 2009 00:45:07 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1635

内容：
写了一点代码来判断astar公开的代码中任意两段代码的相似性。
最关键的是求字符串的编辑距离，O(N^2)，很慢。
于是跑了6个小时，还是2台机器、多个进程同时运行。
但是那个囧到我的astarAnticheat则很快就cha到了我的代码。
问了他怎么回事，然后发现自己做了很挫很挫的事情（详见聊天记录，后附）。

附上用来判相似的代码：
点击这里下载文件

聊天记录如下：
引用
Felix021 00:26:04
今天真是太happy了~

astarAnticheat 00:26:17
挺有意思的

Felix021 00:26:20
第一次跑这么久的程序啊~
你是咋找的相似呢？
很好奇

astarAnticheat 00:27:06
其实是lcs

Felix021 00:27:10
………………………………
我败给你了

astarAnticheat 00:27:21
取一些标点，然后lcs

Felix021 00:27:26
哦
分段
lcs

astarAnticheat 00:27:29
。。。你的技术含量更高

Felix021 00:27:35
我的效率太低
lcs可以优化到O(n)啊
O( n )
edit distance O ( n^2 )，太慢了

astarAnticheat 00:28:55
我只会搞个平方了

算法基础差。。。

Felix021 00:29:15
- -|| 那你跑了多久判到我的啊。。
suffix array我也不会写=.= 只是扫过去而已

astarAnticheat 00:29:52
5点多是就cha到了
但一直没发

Felix021 00:30:19
被你囧到了，哈哈

astarAnticheat 00:30:24
程序大概跑10分钟
呵呵

Felix021 00:30:45
啊？10min？你判多少人啊？

astarAnticheat 00:31:09
第一题只有312个程序
我能拿到的

Felix021 00:31:27
可是总共有48000+种组合啊
O(N^2)哪有那么容易算。。

astarAnticheat 00:31:49
300×300 × 1024×1024

Felix021 00:32:04
我的程序从开始到最后一直在算day1_1，多开了几个线程兼算其他的
day1_1还分开算了
没有1024那么简单吧

astarAnticheat 00:32:50
我的字符串比源程序短，因为只选取标点和数字，把字母都删掉了

Felix021 00:32:51
有一半的代码在3.5K以上啊
哦
这样确实最省事。。
其实我做了很多无用功=.=
标点和数字足够了。。

astarAnticheat 00:33:40
因为考虑到变换变量名啥的，就把字母删掉了

Felix021 00:33:55
嗯，我也是考虑这个，但是还傻乎乎地保留关键字。。。果然挫了
细想一下发现其实没有必要







Generated by Bo-blog 2.1.0