Pattern Matching in C/C++

[abz89]

owh my...
i been worked at levenshtein algo in weeks..
and i got nothing! T.T

yesterday i've found what i'm exactly want!
Needleman–Wunsc h algorithm

i been trying to see the naligner source code too, but i don't understand, how stupid i am T.T

anyone can help me to write this algo in c#, so i can insert the conditional if when insertion/deletion/subs happened,...ple ase, thx u

[jkmyoung]

That algorithm is much more complicated. Even if you have a match, the best thing to do might not be to match them!

At each stage, you calculate 3 possible values:
a. use characters from both strings
b. use 1 char from string 1. (gap penalty)
c. use 1 char from string 2. (gap penalty)

Unfortunately, because of the nature of the algorithm, the truncation detection is much more difficult.

A bad approximation for maximum possible value of 2 remaining strings is
Take the maximum value in that array. max1Value
Assuming length(m) <= length (n), the max value is
max1Value * length(m) - gapPenalty * (length (n - m))
(if n is short, just swap m and n)
After calculating the first possible value, you use that as a best value so far, and truncate branches if they don't fit.

If you want more help, please show how you're laying out this matrix.