A question of CP created by Ishit
BOB AND QUARANTINE
Time limit=1 sec
Bob is at his home currently enjoying his quarantine time by watching movies.However he was recently challanged by his friend Ishit to solve the following problem:
You will be given two strings s1 and s2 such as |s1|>=|s2| you have to print the longest palindromic sequence present in s1 then you have to print the number of times s2 occurs in s1.The problem is fairly simple until now.The challenge is that you have to perform both of these tasks in a linear time complexity that is the time complexity of your code should not exceed O(N) furthermore you are not allowed to use hashing.
Since Bob is enjoying his quarantine period help him write the code.
INPUT:
first line contains the string s1 |s1<100000| and second line contains string s2 |s2<=|s1||.
OUTPUT:
First line containing the longest palindromic subsequence and second line containing the number of times s2 occurs in s1.
Example 1:
Input
abccadbdbcacbaabab
ab
Output
bcabc
3
Example 2:
Input
aaaaaaaaaaaaaaaaaaaaaaaa
aaa
Output
aaaaaaaaaaaaaaaaaaaaaaaa
22
THIS REPO CONTAINS ANSWER TO TWO QUESTIONS 3(CP) AND 4(ML)