Longest Substring Reverse Search

Longest Substring Reverse Search 

PROBLEM STATEMENT :

The program must accept two string values S1 and S2 as the input. The program must print the longest substring of S1 which occurs in S2 in reverse order as the output. If two or more such longest substrings occur in S1, then the program must print the first occurring substring as the output. If there is no such substring, then the program must print -1 as the output.

Boundary Condition(s): 

 1 <= Length of S1, S2 <= 1000

Input Format: 

The first line contains S1. 

The second line contains S2.

Output Format: 

The first line contains the longest substring of S1 which occurs in S2 in reverse order. 

Example Input/Output 1: 
Input: 
monkey 
nomad 

Output: 
mon

Explanation: 

Here S1 = monkey and S2 = nomad. 

The longest substring mon occurs in the string nomad in reverse order. 

So mon is printed as the output. 

Example Input/Output 2: 
Input: 
skillrack 
bankcardsrollingbowllike 

Output: 
kill 

Explanation: 

Here S1 = skillrack and S2 = bankcardsrollingbowllike. The longest substrings which occur in S2 in reverse order are given below. kill rack The string kill occurs first in the string skillrack, so kill is printed as the output. 

Example Input/Output 3: 
Input: 
eggH 
fish 

Output: 
-1

SOLUTION :

C (Programming Language)

      
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverse(char s[])
{
    char temp;
    int l=strlen(s)-1,i=0;
    while(i<l)
    {
        temp=s[i];
        s[i]=s[l];
        s[l]=temp;
        i++;
        l--;
    }
}
int main()
{
    char s1[1001],s2[1001],res[1001]="";
    scanf("%s\n%s",s1,s2);
    reverse(s2);
    int l=strlen(s1),i,cnt;
    for(cnt=0;cnt<l;++cnt)
    {
        for(i=l-cnt-1;i>=0;--i)
        {
            char temp[1001];
            strcpy(temp,s1);
            temp[i+cnt+1]='\0';
            strcpy(temp,temp+i);
            if(strstr(s2,temp))
            {
                strcpy(res,temp);
            }
        }
    }
    if(strcmp(res,"")!=0) printf("%s",res);
    else printf("-1");
}
 

C++ (CPP)

       
#include <bits/stdc++.h>
 
using namespace std;

int main(int argc, char** argv)
{
    string s1,s2,res="";
    cin>>s1>>s2;
    int l=s1.size(),cnt,i;
    reverse(s2.begin(),s2.end());
    for(cnt=0;cnt<l;++cnt)
    {
        for(i=l-cnt-1;i>=0;--i)
        {
            string temp=s1.substr(i,cnt+1);
            if(s2.find(temp)!=std::string::npos)
            {
                res=temp;
            }
        }
    }
    if(res!="") cout<<res;
    else cout<<"-1";
}
 

JAVA

       
import java.util.*;
public class Hello {

    public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String s1=sc.nextLine().trim(),res="";
		String s2=new StringBuilder(sc.next()).reverse().toString();
		int l=s1.length(),cnt,i;
		for(cnt=0;cnt<=l;++cnt)
		{
		    for(i=l-cnt-1;i>=0;--i)
		    {
		        String temp=s1.substring(i,i+cnt+1);
		        if(s2.indexOf(temp)!=-1)
		        {
		            res=temp;
		        }
		    }
		}
		if(res.compareTo("")!=0) System.out.println(res);
		else System.out.println("-1");
	}
}
 

PYTHON

       
s1=input().strip()
s2=input().strip()[::-1]
res=-1
for cnt in range(0,len(s1)):
    for i in range(len(s1)-cnt-1,-1,-1):
        k=s1[i:i+cnt+1]
        if k in s2:
            res=k
print(res if res!=-1 else -1)
 

Never Stop Learning !!