Loading...
Loading...
Loading...
Two attendance machines at the college gate record events as single letters, such as l for a login or s for a scan. Because of network delays, each machine missed some events. Each log is a string of lowercase letters in the order the events were recorded.
The admin wants the longest sequence of events that appears in both logs in the same order. The events do not need to sit next to each other in a log; only their order matters.
Print the length of that longest sequence.
Example 1
Input
lscap sclap
Output
4
scap appears in order in both logs. No sequence of 5 events does.
Example 2
Input
abc def
Output
0
The logs have no event in common.
Try the problem first. Open one hint at a time.
Compare the last events of the two logs. If they match, that event can end the common sequence.
If they differ, one of the two last events is not used. Drop it from one log or from the other, and keep the better result.
Let len[i][j] be the answer for the first i events of log a and the first j events of log b. An empty log gives 0.
Fill the table row by row; every cell needs only the cells above, to the left and diagonally up-left.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor