Incorrect Shift/Border tables are produced by Z-Score Method about algobio

[nictru]

Is it possible that because of the strong shifting rule that is additionally implemented when using the z-boxes, the shifts can be larger while still being safe?
In other words: Do these shift tables even have to be identical?

However, with a certain example (pattern=bbababbaba, text=bbabbababbaba) i managed to enter an infinite loop, which should also be investigated

[Scroogeee]

The script says that border'[j] = j − S[j] for S being the shift table computed by the z-box-method.
Should the method return S or border'?

[nictru]

So apparently you were right with what the hint to S and border'. The original kmp border table calculation calculates a border table, not a shift table - so within the KMP algorithm, we use j-border[j] in order to get back to the shifts. When using z-boxes, we the script shows us how to calculate shift tables, which we then have to convert to border tables manually in order to be able to use them within the same KMP algorithm.

Alternatively, we could have altered the KMP algorithm so that the shift table can be used natively. This way we would not have had to convert the shift table to a border table and then (within KMP) back again. Since this would result in more code, I did not follow this path.

Note, that I also implemented a version of the border table calculation using z-boxes which is based on the mathematical definition instead of the pseudo code. This was helpfull for finding minor flaws in the code.