Skip to content

Commit 2a34d3e

Browse files
committed
1 parent 838a5b1 commit 2a34d3e

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

dynamic_programming/KMPCharacterMatchingAlgorithmInDynamicProgramming.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -398,7 +398,7 @@ With its meaning clear, it is easy to write the code for the search function.
398398

399399
For how to build this `dp` array, you need a secondary state `X`, which is always one state behind the current state `j`, with the same prefix as the longest `j`. We named it "Shadow State".
400400

401-
When constructing the transition direction of the current state `j`, only the character `pat[j]` can advance the state (`dp[j][pat[j]] = j + 1`); for other characters only State fallback, you should ask where the shadow state `X` should fall back (`dp[j][other] = dp[X][other]`, where `other` is other than `pat[j]` all characters).
401+
When constructing the transition direction of the current state `j`, only the character `pat[j]` can advance the state (`dp[j][pat[j]] = j + 1`); for other characters only State fallback, you should ask where the shadow state `X` should fall back (`dp[j][other] = dp[X][other]`, where `other` is other than `pat[j]` all other characters).
402402

403403
For the shadow state `X`, we initialize it to 0 and update it as `j` advances. The update method is very similar to the search process to update `j` (`X = dp[X][pat[j]]`).
404404

0 commit comments

Comments
 (0)