rickard67
O(NP) time complexity does not hold
O(NP) runtime complexity is not achieved (at least not for every case). I double-checked by running demo 1 and adding a counter for the number of times SnakeChrF is called.
As inputs, I passed "aaa..." ('a' repeated N times) and "a a a..." ('a' repeated N times, separated by spaces). Note that P = 0 and thus time complexity should be O(N).
It turns out that, for N greater than 2, the number of calls to SnakeChrF is exactly N * (N - 1) / 2 - 1 (should be easy to verify).
To solve this, the P = 0 case should probably be handled without recursion (as it recurses into more P = 0). Maybe also the P = 1 case.
Sorry I haven't replied, but I'm currently a bit busy and haven't been able to do as much as I would have wanted.
I will look into it eventually though. That said - I wouldn't mind a pull request if you can improve the code yourself.
As far as I can tell O(NP) runtime complexity is achieved inside the repeat loop (in the DiffChr() function). On top of this - a "divide-and-conquer" technique has been applied - which does have an impact on the time complexity (and memory consumption). Different substrings compared to a string (P=0) can yield very different results. Sometime with a time complexity greater than O(N) and sometime much less.
I think it's important to note that the component is only based on the O(NP) Sequence Comparison Algorithm by Sun Wu, Udi Manber & Gene Myers.
Maybe it would be a good idea to create a new unit using the NP algorithm without the divide-and-conquer technique. Especially since most modern computers have a lot more memory than older ones had. I'm just not sure I have the time to do it myself. But you never know...
I do think that the runtime complexity is being achieved in DiffChr() i.e. the runtime of a subproblem is O(NP) plus the runtime of its child subproblems.
And divide-and-conquer is worsening time complexity, but it doesn't have to. If you look at the O(ND) paper ("An O(ND) Difference Algorithm and Its Variations"), section 4b, you'll see that the induction argument for it retaining O(ND) time complexity depends on the assumption that D = 0 and D = 1 problems have linear runtime. The argument can be identically applied to the O(NP) case; the algorithm can be O(NP) if the P = 0 and P = 1 base cases have linear runtime.
What happens with the "a a a..." example I gave before is that N is not split evenly between it's subproblems - it's split into N - 1 and 1, roughly speaking. This is okay for P > 1 as long as P is split evenly. But with P = 0, you end up with something like O(N + (N -1) + (N - 2)...) i.e. O(N^2).
Once you know that P = 0, a subproblem can be easily solved greedily. The P = 1 case is a bit trickier, I think, but you can e.g. find the single insertion/deletion and split there into two P = 0 subproblems.
I'm afraid I'm not at all familiar with Pascal - I came across this project while myself working on an implementation for O(NP) with divide-and-conquer, and I learned just enough Pascal to test what caught my attention (I thought maybe you had somehow managed O(NP) without explicit handling of the base cases).
*There are some other caveats about using O(NP) with divide-and-conquer - the naive implementation may not actually always find a shortest path. I found this blog post by Erik Erlandson which describes it. Also, unlike for D, the Ps of child subproblems may add up to less than the parent problem's P (which is okay, it doesn't really change anything). I also found what I would say is a more elegant solution than the one proposed in the post - just a change in the order in which we update diagonals so that we can still return on the first snake overlap we find.