I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'm dealing with some cryptographic measure with edit distance where algorithm with dynamic programming is not suitable. Please have a look at the algorithm. If we want to do this computation homomorphically, circuit-based computation is needed here which will time consuming one. Usually homomorphic computation works well where there is more additions than multiplications.

enter image description here

This is why, I'm looking for another algorithm rather than the above one.

  • 3
    $\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question to avoid the problems explained there. If you explain your specific situation in more detail, including why the algorithm you've already found is unsuitable, people will be able to recommend something specific, rather than creating a big list and hoping something's useful. $\endgroup$ Jan 28, 2016 at 8:56
  • 2
    $\begingroup$ Please edit the question to explain what research you've done, why you are unhappy with the algorithm you have, and what requirements you want the other algorithms to satisfy. If you already know that you're not happy with one algorithm, then I'm worried that you might be unhappy with other algorithms we suggest too -- unless you tell us why you're unhappy with that algorithm and what requirements you want the other algorithm to satisfy, it's not clear how to help you. $\endgroup$
    – D.W.
    Jan 28, 2016 at 10:12
  • $\begingroup$ I've edited my question. Hopefully it is now better to understand. @David and D.W. $\endgroup$ Jan 28, 2016 at 11:08
  • 1
    $\begingroup$ I appreciate the edit, but it doesn't really address any of the issues pointed out here. You still haven't told us what the requirements are. What I mean is that you need to give us the criteria by which you will evaluate answers, so we can know in advance whether a particular solution will meet your needs. OK, so you want to use the algorithm with some crypto thing -- well, what requirements does that impose on the algorithm? What properties does the algorithm need to have, in order to be useful to you? $\endgroup$
    – D.W.
    Jan 28, 2016 at 18:58
  • $\begingroup$ Question is edited again. Please have a look. @D.W $\endgroup$ Jan 29, 2016 at 2:45

1 Answer 1


The fastest known exact algorithm is due to Masek and Paterson, and runs in time $O(n^2/\log n)$ for two strings of length $n$. Bačkurs and Indyk show that an $O(n^{2-\epsilon})$ algorithm would refute a (somewhat) widely believed conjecture, SETH, and Abboud et al. gave stronger results in this direction.

  • $\begingroup$ Many thanks for the papers. Here, so far I understood, both the authors handle string of same length of n. But I need to handle two string of different lengths. $\endgroup$ Jan 28, 2016 at 11:27
  • $\begingroup$ In fact Masek and Paterson handle the general situation. The lower bounds indeed consider only the case where the two strings have the same length. $\endgroup$ Jan 28, 2016 at 11:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.