Recently I have learned KMP. I am trying to solve the problem for a while but cant understand, What should be my first approach? Can anyone explain me step by step. Any hint would be greatly appreciated.
Problem Link: http://lightoj.com/volume_showproblem.php?problem=1268 Those Who haven't any Lightoj account dont worry just visit the pdf link then you will see the problem statement. Pdf Link: http://lightoj.com/volume_showproblem.php?problem=1268&language=english&type=pdf
Sorry for my poor English. Thanks a lot.
KMP is used to solve the subproblem: Given I matched i characters and add the character c, how many characters now match?
This is same thing as finding longest proper prefix AND suffix of S[1...i]+c which can be done with KMP idea.
for (int i = 1; i < n; i++) { int lps = fail[i]; //calculated from normal kmp dp[i-1][s[i]] = i; for (auto c : characters) dp[i][c] = dp[lps][c]; } dp[n-1][s[n]] = n;However, we don't need to use actual KMP algorithm, just the idea.
for (int i = 1; i < n; i++) { int lps = dp[i-1][s[i]]; dp[i-1][s[i]] = i; for (auto c : characters) dp[i][c] = dp[lps][c]; } dp[n-1][s[n]] = n;To finish the solution you use this data to solve the dp recurrent dp[position][matched]
Thanks.Can you please explain your Pseudocode though I have no idea about dp.
If you consider base case dp[i-1][s[i]] (assuming s is one indexed) thats just i.
Because it means i-1 have matched and now you're adding the i'th character.
For example abradacabra
If you are at "abra" and add a 'd' than now you are at "abrad". But if you add anything else you go back to zero. In other cases you might not go back to zero though.
Now there are two cases for dp[i][c]
1) dp[i][c] = dp[i][s[i+1]] = i+1
2) dp[i][c] build off some earlier prefix
Case one is explained above.
In the second case adding character c to the prefix is NOT the base case. So we build off the next best thing: lps. If that doesn't work, try the next lps, and so on. Same idea behind KMP.
Now for simplifying the implementation (you don't even need to write 'KMP' in first place!) you just have to realize at the point where you loop i that dp[i-1][s[i]] is not yet i. Instead, it is the lps. Why? Because it stores the longest matching prefix/suffix EXCLUDING the whole prefix. Which is the definition of lps.
in this problem apparently need to use aho korasic algorithm instead of KMP
Both will work. As long you create a correct mismatch/failure table. I have tested the described solution on various problems and it works well (USACO, Codeforce, maybe some others)