Problem statement:- Program to Find the Shortest palindromic substring in a string.
Example:-
Input: Given
String=madam acc noon wow abab
Output: Smallest palindrome Substring is wow.
Input: Given
String=python string questions
Output: No palindrome Found
Data requirement:-
Input Data:- str
Output Data:-sub_str1
Additional Data:- in,out,p,len1,minInd,min,flag, sub_str, str_rev
Program in C
Here is the source code of the C Program to Find the Shortest palindromic substring in a string.
Code:
#include<stdio.h>
#include<string.h>
main()
{
int in=0,out=0,p=0,len1,minInd=0,min=0,flag=0;
char str[100]={0},sub_str[100][100]={0},sub_str1[100][100]={0},str_rev[100];
printf("Enter your String:");
gets(str);
//splitting Input String into sub string
while(str[p]!='\0')
{
out=0;
while(str[p]!=' '&&str[p]!='\0')
{
sub_str[in][out]=str[p];
p++;
out++;
}
sub_str[in][out]='\0';
in++;
if(str[p]!='\0')
{
p++;
}
}
int len=in;
p=0;
printf("palindrome Substrings are:\n");
for(in=0;in<len;in++)
{
strcpy(str_rev,sub_str[in]);
if(strcmp(strrev(str_rev),sub_str[in])==0)
{
strcpy(sub_str1[p],sub_str[in]);
printf("%s\n",sub_str1[p]);
p++;
flag=1;
}
}
len=p;
min=strlen(sub_str1[0]);
//finding min length palindrome string from splitting string length
if(flag==1)
{
for(in=0;in<len;in++)
{
len1=strlen(sub_str1[in]);
if(len1<min)
{
min=len1;
minInd=in;
}
}
printf("Smallest palindrome Substring is %s\n",sub_str1[minInd]);
}
else{
printf("No palindrome Found\n");
}
}
Enter your String:madam acc noon wow abab
palindrome Substrings are:
madam
noon
wow
Smallest palindrome Substring is wow
Program in C++
Here is the source code of the C++ Program to Find the Shortest palindromic substring in a string.
Code:
#include<iostream>
#include <cstring>
using namespace std;
char *str_reverse(char *str)
{
int i,len=0,n;
char temp;
len=strlen(str);
n=len-1;
for(i = 0; i <(len/2); i++)
{
temp=str[i];
str[i]=str[n];
str[n]=temp;
n--;
}
return str;
}
main()
{
int in=0,out=0,p=0,len1,minInd=0,min=0,flag=0;
char sub_str[100][100]={0},sub_str1[100][100]={0},str_rev[100];
string str;
cout<<"Enter your String:";
getline(cin,str);
//splitting Input String into sub string
while(str[p]!='\0')
{
out=0;
while(str[p]!=' '&&str[p]!='\0')
{
sub_str[in][out]=str[p];
p++;
out++;
}
sub_str[in][out]='\0';
in++;
if(str[p]!='\0')
{
p++;
}
}
int len=in;
p=0;
cout<<"Palindrome Substrings are:\n";
for(in=0;in<len;in++)
{
strcpy(str_rev,sub_str[in]);
if(strcmp(str_reverse(str_rev),sub_str[in])==0)
{
strcpy(sub_str1[p],sub_str[in]);
cout<<sub_str1[p]<<"\n";
p++;
flag=1;
}
}
len=p;
min=strlen(sub_str1[0]);
//finding min length palindrome string from splitting string length
if(flag==1)
{
for(in=0;in<len;in++)
{
len1=strlen(sub_str1[in]);
if(len1<min)
{
min=len1;
minInd=in;
}
}
cout<<"Smallest palindrome Substring is "<<sub_str1[minInd]<<"\n";
}
else{
cout<<"No palindrome Found."<<"\n";
}
}
Enter your String:redivider deified civic radar level rotor kayak
Palindrome Substrings are:
redivider
deified
civic
radar
level
rotor
kayak
Smallest palindrome Substring is civic
Program in Java
Here is the source code of the Java Program to Find the Shortest palindromic substring in a string.
Code:
import java.util.Scanner;
public class SmallestPalindromicSubstring {
static String reverse(String str_rev)
{
String rev="";
for(int i=str_rev.length();i>0;--i)
{
rev=rev+(str_rev.charAt(i-1));
}
return rev;
}
public static void main(String[] args) {
Scanner cs=new Scanner(System.in);
String str1;
System.out.println("Enter your String:");
str1=cs.nextLine();
str1+=" ";
String[] sub_str=str1.split("\\s");
String[] sub_str1=new String[50];
int in,p=0,flag=0,len1,minInd=0,min=0;
String str_rev="";
System.out.print("Palindrome Substrings are:\n");
for(in=0;in<sub_str.length;in++)
{
str_rev=sub_str[in];
if((reverse(str_rev).compareTo(sub_str[in]))==0)
{
sub_str1[p]=sub_str[in];
System.out.print(sub_str1[p]+"\n");
p++;
flag=1;
}
}
int len=p;
//finding min length palindrome string from splitting string length
if(flag==1)
{
min=sub_str1[0].length();
for(in=0;in<len;in++)
{
len1=sub_str1[in].length();
if(len1<min)
{
min=len1;
minInd=in;
}
}
System.out.print("Smallest palindrome Substring is "+sub_str1[minInd]+"\n");
}
else{
System.out.print("No palindrome Found\n");
}
cs.close();
}
}
Enter your String:
take racecar rat bat fat refer
Palindrome Substrings are:
racecar
refer
Smallest palindrome Substring is refer
Program in Python
Here is the source code of the Python Program to Find the Shortest palindromic substring in a string.
Code:
def reverse(s):
str = ""
for i in s:
str = i + str
return str
str=input("Enter Your String:")
sub_str=str.split(" ")
sub_str1=[]
p=0
flag=0
minInd=0
min=0
str_rev=""
print("Palindrome Substrings are:")
for inn in range(len(sub_str)):
str_rev= sub_str[inn]
if reverse(str_rev).__eq__(sub_str[inn]):
sub_str1.append(sub_str[inn])
print(sub_str1[p])
p +=1
flag = 1
len2 = p
if flag==1:
min = len(sub_str1[0])
for inn in range(0,len2):
len1 = len(sub_str1[inn])
if len1 < min:
min=len1
minInd=inn
print("Smallest palindrome Substring is ",sub_str1[minInd])
else:
print("No palindrome Found")
Enter Your String:madam ask refer wait noon
Palindrome Substrings are:
madam
refer
noon
Smallest palindrome Substring is noon
0 Comments
Please do not Enter any spam link in the comment box