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:

Sample input:_

kitten
sitting

Sample output:

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:

Ranking

Ruby _

Rank	User	Size	Time	Date	Statistics
1	kaki(embed)	12	0.0158	2010/03/26 11:20:01	3B / 2B / 7B
2	gnibbler	12	0.0449	2010/03/26 11:57:27	3B / 2B / 7B

Perl _

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

Python _

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

PHP _

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

Scheme _

Rank	User	Size	Time	Date	Statistics
1	kaki(embed)	43	0.0454	2010/03/26 11:13:24	0B / 29B / 12B
2	kaki(embed)	37	0.2246	2011/03/28 21:37:15	0B / 22B / 13B

Common LISP _

Rank	User	Size	Time	Date	Statistics
1	kozima(embed)	42	0.8946	2010/03/26 08:49:58	0B / 27B / 12B
2	youz	42	0.5511	2010/03/26 23:46:01	0B / 27B / 12B

Arc _

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

Clojure _

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

LilyPond _

Rank	User	Size	Time	Date	Statistics
1	KirarinSnow(embed)	43	2.3225	2010/03/28 09:31:57	0B / 21B / 21B
2	KirarinSnow	62	2.3195	2010/03/28 09:15:43	0B / 38B / 23B

Io _

Rank	User	Size	Time	Date	Statistics
1	pooq	38	0.1708	2012/11/13 18:59:31	0B / 29B / 8B

JavaScript _

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

Lua _

Rank	User	Size	Time	Date	Statistics
1	pooq	42	0.0022	2010/08/15 17:22:41	0B / 20B / 22B

Xtal _

Rank	User	Size	Time	Date	Statistics
1	pooq	41	0.0614	2010/03/27 17:30:56	0B / 21B / 20B

Icon _

Rank	User	Size	Time	Date	Statistics
1	pooq	55	0.0508	2012/04/05 06:51:09	0B / 36B / 16B

REXX _

Rank	User	Size	Time	Date	Statistics
1	pooq	38	0.0452	2012/04/12 19:30:41	0B / 23B / 12B

Cyan _

Rank	User	Size	Time	Date	Statistics
1	pooq	50	2.9695	2010/08/23 18:50:04	0B / 26B / 24B

Prolog _

Rank	User	Size	Time	Date	Statistics
1	pooq	47	0.0995	2010/03/27 05:56:28	0B / 28B / 17B
2	j2e2xae	42	0.0604	2025/01/31 18:36:37	0B / 22B / 17B

Forth _

Rank	User	Size	Time	Date	Statistics
1	j2e2xae	24	0.0702	2025/02/01 08:26:49	0B / 16B / 1B

BASIC _

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

Perl6 _

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

Erlang _

Rank	User	Size	Time	Date	Statistics
1	51b(embed)	76	0.3810	2010/03/28 16:45:48	0B / 42B / 27B
2	gnibbler	77	0.3771	2010/03/26 14:35:20	0B / ?B / ?B

J _

Rank	User	Size	Time	Date	Statistics
1	pooq	25	0.0865	2010/03/26 23:41:48	0B / 14B / 7B

K _

Rank	User	Size	Time	Date	Statistics
1	pooq	13	0.0681	2012/03/19 20:09:49	0B / 7B / 4B

C _

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

Go _

Rank	User	Size	Time	Date	Statistics
1	gnibbler	62	0.0220	2010/03/26 15:31:24	0B / ?B / ?B

OCaml _

Rank	User	Size	Time	Date	Statistics
1	m.ukai (embed)	41	0.1325	2010/09/20 15:52:45	0B / 25B / 15B

Haskell _

Rank	User	Size	Time	Date	Statistics
1	notogawa(embed)	46	0.0016	2010/03/25 20:51:31	0B / 27B / 13B
2	rst76(embed)	46	0.0375	2010/03/28 00:18:12	0B / 27B / 13B
3	Lost_dog(embed)	46	0.0275	2010/03/28 14:31:54	0B / 28B / 12B
4	TAKO/j0nKI	50	0.0016	2010/03/25 04:03:24	0B / 28B / 16B

Java _

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

Pascal _

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

Fortran _

Rank	User	Size	Time	Date	Statistics
1	gnibbler	44	0.0003	2010/03/26 13:27:48	0B / ?B / ?B

C# _

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

LMNtal _

Rank	User	Size	Time	Date	Statistics
1	pooq	59	1.3769	2011/03/28 21:08:43	0B / 37B / 22B

Maxima _

Rank	User	Size	Time	Date	Statistics
1	pooq	36	0.2280	2010/03/27 10:16:34	0B / 21B / 15B

AWK _

Rank	User	Size	Time	Date	Statistics
1	nn	21	0.0203	2010/03/26 16:19:23	0B / 8B / 13B

sed _

Rank	User	Size	Time	Date	Statistics
1	:)(cheat)(:	22	0.0012	2010/03/25 05:39:58	0B / 12B / 7B
2	msk	24	0.0238	2010/03/29 02:00:10	0B / 12B / 9B
3	KirarinSnow(cheat)	26	0.0012	2010/03/25 13:11:43	0B / 15B / 8B

jq _

Rank	User	Size	Time	Date	Statistics
1	pooq	19	0.0316	2019/09/24 15:38:29	0B / ?B / ?B

wake _

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

bc _

Rank	User	Size	Time	Date	Statistics
1	Carlos Gutierrez	49	0.0265	2010/03/28 13:36:30	0B / ?B / ?B
2	gnibbler	50	0.0012	2010/03/26 06:08:39	0B / 31B / 17B
3	teebee	43	0.0022	2011/07/06 07:27:49	0B / 29B / 11B

Postscript _

Rank	User	Size	Time	Date	Statistics
1	51b(bin)(embed)	21	0.2664	2010/03/28 14:29:25	7B / 12B / 1B
2	yshl(bin)(embed)	21	0.2634	2010/03/28 21:20:51	9B / 11B / 1B
3	yshl(embed)	30	0.2664	2010/03/28 15:10:12	0B / 22B / 1B

R _

Rank	User	Size	Time	Date	Statistics
1	pooq	25	0.5135	2010/03/27 11:10:29	0B / 16B / 9B

QCL _

Rank	User	Size	Time	Date	Statistics
1	pooq	115	0.0376	2010/03/27 07:58:53	0B / 89B / 21B

GolfScript _

Rank	User	Size	Time	Date	Statistics
1	gnibbler	9	0.1202	2010/03/26 00:37:31	0B / ?B / ?B
2	KirarinSnow(cheat,bin)	13	0.1129	2010/03/25 13:27:08	0B / 6B / 5B
3	KirarinSnow(cheat)	13	0.1134	2010/03/25 13:27:14	0B / 6B / 5B

gs2 _

Rank	User	Size	Time	Date	Statistics
1	whio	6	0.2331	2017/04/28 03:10:00	4B / 1B / 1B

FlogScript _

Rank	User	Size	Time	Date	Statistics
1	pooq	15	0.1222	2010/09/09 21:42:56	0B / 6B / 7B

z80 _

Rank	User	Size	Time	Date	Statistics
1	j2e2xae	27	0.0476	2025/02/01 07:20:32	10B / 9B / 5B

Vim _

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

goruby _

Rank	User	Size	Time	Date	Statistics
1	murky-satyr	12	0.0937	2010/03/26 14:20:21	0B / 6B / 5B
2	gnibbler	13	0.0930	2010/03/26 13:19:41	0B / ?B / ?B

Groovy _

Rank	User	Size	Time	Date	Statistics
1	murky-satyr	30	3.4267	2010/03/31 01:27:53	0B / 21B / 7B
2	gnibbler	31	3.4335	2010/03/26 14:23:23	0B / ?B / ?B

Scala _

Rank	User	Size	Time	Date	Statistics
1	pooq	31	9.9482	2011/02/18 05:10:20	0B / 22B / 9B

Logo _

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	Forth	j2e2xae	24	2500
19	J	pooq	25	2400
20	R	pooq	25	2400
21	Clojure	pooq	27	2222
22	Logo	pooq	27	2222
23	z80	j2e2xae	27	2222
24	wake	murky-satyr	28	2142
25	BASIC	yuko	30	2000
26	Groovy	murky-satyr	30	2000
27	C	inaniwa(embed)	31	1935
28	Scala	pooq	31	1935
29	Maxima	pooq	36	1666
30	Pascal	yuko	36	1666
31	Scheme	kaki(embed)	37	1621
32	REXX	pooq	38	1578
33	Io	pooq	38	1578
34	Xtal	pooq	41	1463
35	OCaml	m.ukai (embed)	41	1463
36	Common LISP	kozima(embed)	42	1428
37	Lua	pooq	42	1428
38	Prolog	j2e2xae	42	1428
39	LilyPond	KirarinSnow(embed)	43	1395
40	bc	teebee	43	1395
41	Fortran	gnibbler	44	1363
42	Haskell	notogawa(embed)	46	1304
43	Cyan	pooq	50	1200
44	Icon	pooq	55	1090
45	LMNtal	pooq	59	1016
46	Go	gnibbler	62	967
47	Java	gnibbler	66	909
48	Erlang	51b(embed)	76	789
49	C#	TAKO/j0nKI	111	540
50	QCL	pooq	115	521

return to the top page