ADAPHOTO - Ada and Terramorphing
Ada the Ladybug was already on two trips this year. She visited two countries: Republic of Bugongo and Democratic Republic of Bugongo. Even though those countries are completely different and far far away from each other, Ada found some similarities. Now she is looking at photos from each of those countries and examines similarities. Sadly, both of the sequences of photos are very long so she can't handle it herself.
The sequence of photos is sequence of following terrestrial formations: A hill (^), a valley (v), a plain (-), a lake ~
Find the longest common contiguous subsequence between the two sequences of photos.
Important note: Terramorphism is very difficult process. One can't easily influence it so each of the terrestrial formation is generated with more or less 25%.
Input
The first two and the only lines of input contiguous first and second sequence of photos 1 ≤ |s1|, |s2| ≤ 106
Output
For each test-cases, print the longest common sequence.
Example Input
-~^v- ^--v
Example Output
1
Example Input 2
-~ -~v^^^^^v-
Example Output 2
2
Example Input 3
~-~-v--~^ ~^--^~-v
Example Output 3
3
Example Input 4
^^^v-v^^v-v-v~v- vv^v-^~~^v^~^vv~^^-
Example Output 4
3
Example Input 5
~~~vv~-~~vv~v-v--~-^-~^~-^^ ~^~--v~-
Example Output 5
4
hide comments
|
jinseo0601:
2024-05-02 21:43:14
sa-is algorithm o(n). solved it. |
|
mahbubkuet08:
2021-10-24 12:06:21
My submission is with rolling hash with complexity O((log m) * (n)). Gives me WA, |
|
rohit_goyal:
2021-04-25 20:34:49
My Suffix Automaton barely passed. |
|
violet_user:
2019-10-29 22:26:03
I can't solve suffix array by O(nlogn) with only static arrays... @Morass help please, or say that this task for hashes Last edit: 2019-10-29 22:28:08 |
|
spojmaster_9:
2019-08-17 16:49:26
i somehow solve it by suffix array O(nlogn^2), and my O(nlogn) just tle, the constrain 2*1e6 is too big for using vector |
|
gang_leader:
2019-07-12 16:15:20
Maybe suffix array |
|
kaushalag29:
2018-09-23 16:59:16
@Morass The problem statement says to print the longest common contiguous subsequence.But the output shows length of longest common subsequence.Hashing gives WA,Double Hashing gives TLE.Plz Check my solution. |
| Added by: | Morass |
| Date: | 2017-08-30 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS