Forward Backward Sub-String Search

Problem Statement: You are given an input string A[1…n].Of all the sub-strings of A,find the longest sub-string ‘s’ such that ‘s’ appears both forward and backward in A. The forward and backward sub-strings should not overlap. For example, for the input string “SAWMWASING”, the output should be “SAW”. For the input string “DYNAMICPROGRAMANYTIMES”, the output should be “YNAM”.

Solution:

import java.util.*;
class bkfw
{
public static void main(String args[])
{
String str,s1,s2;
int n,i,j,k,a=0,index=0;
Scanner sc=new Scanner(System.in);
System.out.println(“Enter a string”);
str=sc.nextLine();
n=str.length();
StringBuffer st= new StringBuffer(str);
String s[]=new String[20];
for(i=0;i<Math.round((float)n/2);i++) //rounding off for odd no of alphabets in the string
for(j=2;j<Math.round((float)n/2);j++) //j defines length of string,minimum length of string is taken as 2
for(k=0;k+j<st.length();k++)
{
s1=str.substring(i,i+j);
st.replace(0,st.length(),str.substring(i+j));
st.reverse(); //only reversing rest of the string to avoid overlapping
s2=st.substring(k,k+j);
if (s1.equals(s2))
{
s[a]=s1;
a++;
}
}
if(a>0)
{
n=s[0].length();
for(i=0;i<a;i++)
if(n<s[i].length())
{
n=s[i].length();
index=i;
}
System.out.println(s[index]+” is the longest substring that repeats backwards and forwards”);
}
else
System.out.println(“no such substring exists that repeats backwards and forwards”);
}
}

Cyclic Rotation of String

Problem Statement: A cyclic rotation of a string is obtained by chopping off a prefix of the string and attaching it to the end.For example,”katankal” is a cyclic rotation of the string”alkatank”.You are given two strings p[1…n] and t[1…m].Write a program to determine whether p is a cyclic rotation of t.

Solution:

import java.util.*;
class cycrot
{
public static void main(String args[])
{
int i=0,j,k,cr1=0,cr2=0;
String st,str;
Scanner sc=new Scanner(System.in);
System.out.println(“enter string”);
st=sc.nextLine();
System.out.println(“enter string”);
str=sc.nextLine();
char p[]=new char[st.length()];
char t[]=new char[str.length()];
p=st.toCharArray();
t=str.toCharArray();
for(j=0;j<str.length();j++)
{
if(p[0]==t[j])
{
for(i=0,k=j;k<str.length();k++,i++)
{
if(p[i]==t[k])
cr1=1;
else
{
cr1=0;
break;
}
}
}
}
if(p[i]==t[0])
{
for(j=0;i<st.length();i++,j++)
if (p[i]==t[j])
cr2=1;
else
{
cr2=0;
break;
}
}
if (cr1==1 && cr2==1)
System.out.println(st+” is a cyclic rotation of “+str);
else
System.out.println(st+” is not a cyclic rotation of “+str);
}
}

Modified Stack Implementation

Problem Statement: Stack is a data structure that supports LIFO(Last in First out).Implement a modified version of Stack,which pops out the most frequently added item.

Solution:

import java.util.*;
class stack
{
int arr[][]=new int[20][2];
int top=-1;
void push(int n)
{
if(top==19)
System.out.println(“Stack full”);
else
{
int count,i,j;
top++;
arr[top][0]=n;
}
}
int pop()
{
int n=-1;
if(top==-1)
System.out.println(“Stack empty”);
else
{
int i,j,temp,temp1,count;
for(i=0;i<=top;i++)
{
count=0;
for(j=0;j<=top;j++)
if(arr[i][0]==arr[j][0])
arr[i][1]=++count;
}
for(i=0;i<=top;i++)
for(j=0;j<=top-1;j++)
if(arr[j][1]>arr[j+1][1])
{
temp=arr[j][0];
temp1=arr[j][1];
arr[j][0]=arr[j+1][0];
arr[j][1]=arr[j+1][1];
arr[j+1][0]=temp;
arr[j+1][1]=temp1;
}
n=arr[top][0];
top–;
}
return n;
}
}
class modifiedStack
{
public static void main(String args[])
{
int option,n;
Scanner sc=new Scanner(System.in);
stack s=new stack();
System.out.println(“Modified Stack implementation”);
do
{
System.out.println(“Choose a given option”);
System.out.println(“1.Push”);
System.out.println(“2.Pop”);
System.out.println(“3.Exit”);
option=sc.nextInt();
switch(option)
{
case 1:System.out.println(“Enter a number”);
n=sc.nextInt();
s.push(n);
break;
case 2:n=s.pop();
if(n!=-1)
System.out.println(n+” was popped”);
break;
}
}while(option!=3);
}
}

Wedge Patterns

1. Write a program to print the following pattern:

12344321

123**321

12****21

1******1

Accept the number of lines from the user.(Here n=4)

Solution:

import java.util.*;
class pattern10
{
public static void main(String args[])
{
int i,j,n;
Scanner sc=new Scanner(System.in);
System.out.println(“Enter a number”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(j<n-i)
System.out.print(j+1);
else
System.out.print(“*”);
for(j=n;j>0;j–)
if(j>n-i)
System.out.print(“*”);
else
System.out.print(j);
System.out.println();
}
}
}

 

2. Write a program to print the following pattern:

 

Accept the number of lines from the user.(Here n=5)

Solution:

import java.util.*;
class pattern11
{
public static void main(String args[])
{
int i,j,n;
Scanner sc=new Scanner(System.in);
System.out.println(“Enter a number”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(j<=i)
System.out.print(j+1);
else
System.out.print(” “);
for(j=n;j>0;j–)
if(j>i+1)
System.out.print(” “);
else
System.out.print(j);
System.out.println();
}
}
}

Simple Patterns

 

1. Write a program to print the following pattern:

5432*

543*1

54*21

5*321

*4321

Accept the number of lines from the user.(Here n=5)

Solution:

import java.util.*;
class pattern7
{
public static void main(String args[])
{
int i,j,n;
Scanner sc=new Scanner(System.in);
System.out.println("Enter a Number");
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=n;j>0;j--)
if(j==i+1)
System.out.print("*");
else
System.out.print(j);
System.out.println();
}
}
}


2. Write a program to print the following pattern:

55555
45555
34555
23455
12345

Accept the number of lines from the user.(Here n=5)

Solution:

import java.util.*;
class pattern8
{
public static void main(String args[])
{
int i,j,n,count;
Scanner sc=new Scanner(System.in);
System.out.println("Enter a Number");
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=n-i,count=0;count<n;count++,j++)
if(j<n)
System.out.print(j);
else
System.out.print(n);
System.out.println();
}
}
}


3. Write a program to print the following pattern:

1
2*2
3*3*3
4*4*4*4
4*4*4*4
3*3*3
2*2
1

Accept the number of lines from the user.(Here n=4)

Solution:

import java.util.*;
class pattern9
{
public static void main(String args[])
{
int i,j,n;
Scanner sc=new Scanner(System.in);
System.out.println("Enter a Number");
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<2*i+1;j++)
if(j%2==0)
System.out.print(i+1);
else
System.out.print("*");
System.out.println();
}
for(i=n;i>0;i--)
{
for(j=0;j<2*i-1;j++)
if(j%2==0)
System.out.print(i);
else
System.out.print("*");
System.out.println();
}
}
}

Whirl Pattern

Write a program to print the following pattern:

1    2    3    4    5    6    7    8   9   10

36  37  38  39  40  41  42  43  44  11

35  64  65  66  67  68  69  70  45  12

34  63  84  85  86  87  88  71  46  13

33  62  83  96  97  98  89  72  47  14

32  61  82  95  100 99  90  73  48  15

31  60  81  94  93  92  91  74  49  16

30  59  80  79  78  77  76  75  50  17

29  58  57  56  55  54  53  52  51  18

28  27  26  25  24  23  22  21  20  19

Accept the number  from the user.(Here n=10)

Solution:

import java.util.*;
class whirl
{
public static void main(String args[])
{
int i,j,no=1,n,count=0,m;
System.out.println(“Enter a number”);
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int matrix[][]=new int[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
matrix[i][j]=0;
for(i=0,j=0;count<Math.round((float)n/2);i++,j++,count++)
{
for(;j<n && matrix[i][j]==0;j++)
{
matrix[i][j]=no;
no++;
}
for(j–;i<n-1 && matrix[i+1][j]==0;)
{
matrix[++i][j]=no;
no++;
}
for(;j>0 && matrix[i][j-1]==0;)
{
matrix[i][–j]=no;
no++;
}
for(i–;i>0 && matrix[i][j]==0;i–)
{
matrix[i][j]=no;
no++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
System.out.print(matrix[i][j]+” “);
System.out.println();
}
}
}

Kaju katri patterns :p

1.Write a program to print the following pattern:

Accept the number of lines from the user.

Solution:

import java.util.*;
class pattern5
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j;
System.out.println(“Enter the number of lines”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
System.out.print(” “);
for(j=0;j<2*i+1;j++)
System.out.print(“*”);
System.out.println();
}
for(i=0;i<n-1;i++)
{
for(j=0;j<i+1;j++)
System.out.print(” “);
for(j=0;j<2*n-2*i-3;j++)
System.out.print(“*”);
System.out.println();
}
}
}

 

2. Write a program to print the following pattern:

Accept the number of lines from the user.

Solution:

import java.util.*;
class pattern6
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j,count;
System.out.println(“Enter the number of lines”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<2*n+1;j++)
if(j==n-i)
for(count=0;count<2*i;count++,j++)
System.out.print(” “);
else
System.out.print(“*”);
System.out.println();
}
for(i=0;i<n-1;i++)
{
for(j=0;j<2*n+1;j++)
if(j==i+2)
for(count=0;count<2*n-2*i-4;count++,j++)
System.out.print(” “);
else
System.out.print(“*”);
System.out.println();
}
}
}

Triangle Patterns(Numbered)

1.Write a program to print the following pattern:

Accept the number of lines from the user.

Solution:

import java.util.*;
class pattern3
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j,k;
System.out.println(“Enter the number of lines”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
System.out.print(” “);
for(j=0,k=i+1;j<2*i+1;j++)
{
System.out.print(k);
if(j<i)
k++;
else
k–;
}
System.out.println();
}
}
}

 

2.Write a program to print the following pattern:

1

2 4

1 3 5

2 4 6 8

1 3 5 7 9

Accept the number of lines from the user.

Solution:

import java.util.*;
class pattern4
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j,count;
System.out.println(“Enter the number of lines”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
if(i%2==0)
for(count=0,j=1;count<i+1;count++,j+=2)
System.out.print(j);
else
for(count=0,j=2;count<i+1;count++,j+=2)
System.out.print(j);
System.out.println();
}
}
}

Triangle Patterns

1.Write a program to print the following pattern:

Accept the number of lines from the user.

Solution:

import java.util.*;
class pattern1
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j;
System.out.println(“Enter the number of lines”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
System.out.print(” “);
for(j=0;j<2*i+1;j++)
System.out.print(“*”);
System.out.println();
}
}
}

 

2.Write a program to print the following pattern:

Accept the number of lines from the user.

Solution:

import java.util.*;
class pattern2
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j;
System.out.println(“Enter the number of lines”);
n=sc.nextInt();
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
System.out.print(” “);
for(j=0;j<2*i+1;j++)
if(j%2==0)
System.out.print(“*”);
else
System.out.print(“A”);
System.out.println();
}
}
}