Levenshtein Distance
Submit
Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.
Problem
http://en.wikipedia.org/wiki/Levenshtein_Distance
Options
exec is denied
now post-mortem time, all source codes will be revealed
Sample input:_
0123456789abcdefghijklmnopqrstuvwxyz
0123456789abcdefghijklmnopqrstuvwxyz
Sample output:
0
Sample input:_
kitten
sitting
Sample output:
3
Sample input:_
In approximate string matching, the objective is to find matches for short strings, for instance, strings from a dictionary, in many longer texts, in situations where a small number of differences is to be expected. Here, one of the strings is typically short, while the other is arbitrarily long. This has a wide range of applications, for instance, spell checkers, correction systems for optical character recognition, and software to assist natural language translation based on translation memory.The Levenshtein distance can also be computed between two longer strings, but the cost to compute it, which is roughly proportional to the product of the two string lengths, makes this impractical.
In:papproximate:pstring:pmatching,:pthe:pobjective:pis:pto:pfind:pmatches:pfor:pshort:pstrings,:pfor:pinstance,:pstrings:pfrom:pa:pdictionary,:pin:pmany:plonger:ptexts,:pin:psituations:pwhere:pa:psmall:pnumber:pof:pdifferences:pis:pto:pbe:pexpected.:pHere,:pone:pof:pthe:pstrings:pis:ptypically:pshort,:pwhile:pthe:pother:pis:parbitrarily:plong.:pThis:phas:pa:pwide:prange:pof:papplications,:pfor:pinstance,:pspell:pcheckers,:pcorrection:psystems:pfor:poptical:pcharacter:precognition,:pand:psoftware:pto:passist:pnatural:planguage:ptranslation:pbased:pon:ptranslation:pmemory.The:pLevenshtein:pdistance:pcan:palso:pbe:pcomputed:pbetween:ptwo:plonger:pstrings,:pbut:pthe:pcost:pto:pcompute:pit,:pwhich:pis:proughly:pproportional:pto:pthe:pproduct:pof:pthe:ptwo:pstring:plengths,:pmakes:pthis:pimpractical.
Sample output:
214
Ranking
Rank | User | Size | Time | Date | Statistics |
---|
1 | gnibbler | 18 | 0.0224 | 2010/03/26 11:44:49 | 0B / 12B / 5B |
2 | dcutter | 26 | 0.0262 | 2010/03/29 20:34:10 | 0B / 12B / 14B |
3 | TAKO/j0nKI | 33 | 0.0003 | 2010/03/25 03:32:57 | 0B / 22B / 10B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | gnibbler | 21 | 0.0557 | 2010/03/26 13:16:05 | 0B / ?B / ?B |
2 | hallvabo | 21 | 0.0558 | 2010/04/01 00:00:57 | 0B / 15B / 5B |
3 | recursive | 22 | 0.0589 | 2010/03/26 00:31:44 | 0B / 15B / 6B |
4 | tobiesque | 23 | 0.0460 | 2010/03/25 09:27:41 | 0B / 14B / 9B |
5 | JJeep | 39 | 0.0562 | 2010/03/26 12:01:41 | 0B / 24B / 14B |
6 | showyou | 42 | 0.0606 | 2010/03/28 02:10:30 | 2B / ?B / ?B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | gnibbler | 20 | 0.0699 | 2010/03/26 13:52:02 | 0B / ?B / ?B |
2 | o-cn | 21 | 0.0484 | 2010/03/29 10:11:37 | 0B / 13B / 8B |
3 | TAKO/j0nKI | 29 | 0.0507 | 2010/03/25 03:10:29 | 0B / 15B / 14B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 22 | 3.3853 | 2010/03/27 05:21:44 | 0B / 12B / 8B |
2 | murky-satyr | 23 | 3.3711 | 2010/03/27 05:35:45 | 4B / 10B / 8B |
3 | youz | 33 | 3.9203 | 2010/03/26 23:46:20 | 0B / 18B / 13B |
4 | gnibbler | 34 | 3.3962 | 2010/03/26 14:07:04 | 0B / ?B / ?B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 27 | 2.9420 | 2010/03/27 05:33:25 | 0B / 15B / 9B |
2 | murky-satyr | 27 | 2.9576 | 2010/03/27 05:45:58 | 0B / 15B / 9B |
3 | gnibbler | 31 | 2.9310 | 2010/03/26 14:26:37 | 0B / ?B / ?B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 38 | 0.1708 | 2012/11/13 18:59:31 | 0B / 29B / 8B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | ktt | 24 | 0.0004 | 2010/03/25 10:34:16 | 0B / 17B / 6B |
2 | murky-satyr | 24 | 0.0375 | 2010/03/31 01:20:06 | 0B / 17B / 6B |
3 | gnibbler | 25 | 0.0156 | 2010/03/26 14:55:46 | 0B / ?B / ?B |
4 | TAKO/j0nKI | 28 | 0.0003 | 2010/03/25 03:15:47 | 0B / 18B / 9B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 42 | 0.0022 | 2010/08/15 17:22:41 | 0B / 20B / 22B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 41 | 0.0614 | 2010/03/27 17:30:56 | 0B / 21B / 20B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 55 | 0.0508 | 2012/04/05 06:51:09 | 0B / 36B / 16B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 38 | 0.0452 | 2012/04/12 19:30:41 | 0B / 23B / 12B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 50 | 2.9695 | 2010/08/23 18:50:04 | 0B / 26B / 24B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 47 | 0.0995 | 2010/03/27 05:56:28 | 0B / 28B / 17B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | *yuko* | 30 | 1.8154 | 2010/03/26 19:48:26 | 2B / 15B / 13B |
2 | gnibbler | 32 | 2.1181 | 2010/03/26 14:53:01 | 0B / ?B / ?B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | dcutter | 65 | 2.3725 | 2010/03/29 20:46:54 | 0B / 38B / 21B |
2 | pooq | 18 | 6.5300 | 2010/08/10 13:22:27 | 0B / 12B / 4B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 25 | 0.0865 | 2010/03/26 23:41:48 | 0B / 14B / 7B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 13 | 0.0681 | 2012/03/19 20:09:49 | 0B / 7B / 4B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | inaniwa(embed) | 31 | 0.0003 | 2010/03/25 13:04:46 | 2B / 16B / 13B |
2 | not | 31 | 0.0148 | 2010/03/25 20:00:53 | 2B / 16B / 13B |
3 | nai(embed) | 31 | 0.0004 | 2010/03/25 22:20:32 | 2B / 16B / 13B |
4 | msk(rand) | 37 | 0.0003 | 2010/03/25 06:46:38 | 0B / 20B / 17B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | gnibbler | 66 | 0.2802 | 2010/03/26 13:42:21 | 0B / ?B / ?B |
2 | hallvabo | 66 | 0.2889 | 2010/04/01 00:06:04 | 0B / 46B / 19B |
3 | nattow | 73 | 0.2839 | 2010/03/31 13:40:40 | 0B / 47B / 25B |
4 | mulder_fbi | 78 | 0.2784 | 2010/03/25 06:13:08 | 0B / 50B / 27B |
5 | TAKO/j0nKI | 79 | 0.2821 | 2010/03/25 04:00:58 | 0B / 55B / 23B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | *yuko* | 36 | 0.0481 | 2010/03/30 20:44:19 | 0B / 27B / 8B |
2 | gnibbler | 37 | 0.0467 | 2010/03/30 16:33:40 | 0B / ?B / ?B |
3 | uru | 48 | 0.0705 | 2010/03/29 22:34:28 | 0B / 32B / 13B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | TAKO/j0nKI | 111 | 0.1614 | 2010/03/26 20:02:11 | 0B / 78B / 27B |
2 | Hex | 130 | 0.1911 | 2010/03/26 09:05:31 | 0B / ?B / ?B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 59 | 1.3769 | 2011/03/28 21:08:43 | 0B / 37B / 22B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 36 | 0.2280 | 2010/03/27 10:16:34 | 0B / 21B / 15B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | nn | 21 | 0.0203 | 2010/03/26 16:19:23 | 0B / 8B / 13B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 19 | 0.0316 | 2019/09/24 15:38:29 | 0B / ?B / ?B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | murky-satyr | 28 | 0.0200 | 2010/08/05 15:05:04 | 0B / 7B / 18B |
2 | pooq | 29 | 0.0116 | 2010/07/20 13:07:36 | 0B / 8B / 18B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 25 | 0.5135 | 2010/03/27 11:10:29 | 0B / 16B / 9B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 115 | 0.0376 | 2010/03/27 07:58:53 | 0B / 89B / 21B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | whio | 6 | 0.2331 | 2017/04/28 03:10:00 | 4B / 1B / 1B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 15 | 0.1222 | 2010/09/09 21:42:56 | 0B / 6B / 7B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pla | 20 | 0.4378 | 2010/03/31 02:56:57 | 0B / 12B / 5B |
2 | nn | 21 | 0.0653 | 2010/03/30 11:23:19 | 0B / 12B / 7B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 31 | 9.9482 | 2011/02/18 05:10:20 | 0B / 22B / 9B |
Rank | User | Size | Time | Date | Statistics |
---|
1 | pooq | 27 | 2.5098 | 2011/03/20 00:58:09 | 0B / 20B / 2B |
Language Ranking_
Rank | Lang | User | Size | Score |
1 | gs2 | whio | 6 | 10000 |
2 | GolfScript | gnibbler | 9 | 6666 |
3 | Ruby | kaki(embed) | 12 | 5000 |
4 | goruby | murky-satyr | 12 | 5000 |
5 | K | pooq | 13 | 4615 |
6 | FlogScript | pooq | 15 | 4000 |
7 | Perl | gnibbler | 18 | 3333 |
8 | Perl6 | pooq | 18 | 3333 |
9 | jq | pooq | 19 | 3157 |
10 | PHP | gnibbler | 20 | 3000 |
11 | Vim | pla | 20 | 3000 |
12 | Python | gnibbler | 21 | 2857 |
13 | AWK | nn | 21 | 2857 |
14 | Postscript | 51b(bin)(embed) | 21 | 2857 |
15 | sed | :)(cheat)(: | 22 | 2727 |
16 | Arc | pooq | 22 | 2727 |
17 | JavaScript | ktt | 24 | 2500 |
18 | J | pooq | 25 | 2400 |
19 | R | pooq | 25 | 2400 |
20 | Clojure | pooq | 27 | 2222 |
21 | Logo | pooq | 27 | 2222 |
22 | wake | murky-satyr | 28 | 2142 |
23 | BASIC | *yuko* | 30 | 2000 |
24 | Groovy | murky-satyr | 30 | 2000 |
25 | C | inaniwa(embed) | 31 | 1935 |
26 | Scala | pooq | 31 | 1935 |
27 | Maxima | pooq | 36 | 1666 |
28 | Pascal | *yuko* | 36 | 1666 |
29 | Scheme | kaki(embed) | 37 | 1621 |
30 | REXX | pooq | 38 | 1578 |
31 | Io | pooq | 38 | 1578 |
32 | Xtal | pooq | 41 | 1463 |
33 | OCaml | m.ukai (embed) | 41 | 1463 |
34 | Common LISP | kozima(embed) | 42 | 1428 |
35 | Lua | pooq | 42 | 1428 |
36 | LilyPond | KirarinSnow(embed) | 43 | 1395 |
37 | bc | teebee | 43 | 1395 |
38 | Fortran | gnibbler | 44 | 1363 |
39 | Haskell | notogawa(embed) | 46 | 1304 |
40 | Prolog | pooq | 47 | 1276 |
41 | Cyan | pooq | 50 | 1200 |
42 | Icon | pooq | 55 | 1090 |
43 | LMNtal | pooq | 59 | 1016 |
44 | Go | gnibbler | 62 | 967 |
45 | Java | gnibbler | 66 | 909 |
46 | Erlang | 51b(embed) | 76 | 789 |
47 | C# | TAKO/j0nKI | 111 | 540 |
48 | QCL | pooq | 115 | 521 |
return to the top page