It's fun to think of the regular expression which matches all strings off by Lev... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		jhallenworld on June 18, 2015 \| parent \| context \| favorite \| on: Levenshtein automata can be simple and fast It's fun to think of the regular expression which matches all strings off by Levenshtein=1. For "hello" it's something like: hello\|ello\|hllo\|helo\|hell\|.hello\|h.ello\|he.llo\|hel.lo\|hell.o\|hello.\|.ello\|h.llo\|he.lo\|hel.o\|hell. This seems pretty easy to generate the NFA for this, then compile it to a DFA as usual.

TheLoneWolfling on June 18, 2015 | [–]

The problem with this approach is that it can be (absurdly) complex to generate, even when the actual DFA output required is small.

Look at the intermediates generated by something like "hhhhh". There is a massive amount of redundancy there.

fenollp on June 18, 2015 | [–]

Or: hello|.?ello|h.?llo|he.?lo|hel.?o|hell.?

cousin_it on June 18, 2015 | [–]

That doesn't match "helloo".

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact