A

Practical File
On

ADVANCED ALGORITHM Lab. (MTCS-152)

Submitted in partial fulfilment of the requirement for award of the degree

of

Master of Technology
In
Computer Science & Engineering

Submitted To: - Submitted By:-

Ms. Swapna Singh Abhishek Tiwari

Assistant Professor Roll. No.:5466669

C.S.E. Department Semester - 1st

IPEC, Ghaziabad M.Tech (CSE)

Department of Computer Science & Engineering

Inderprastha Engineering College, Ghaziabad
 INDEX
AA Lab. (MTCS-152)
Student Name: Abhishek Tiwari Roll No. 5466669

Sr. No. Name of Experiment Date Signature

Write Java programs that use both recursive and non-recursive
1. functions for implementing the following searching methods:
a) Linear search b) Binary search
Write a Java program to implement all the functions of a
2.
dictionary (ADT) using Hashing.
Write Java programs for implementing the following sorting
3. methods: a) Bubble sort b) Insertion sort c) Quick sort d)
Merge sort e) Heap sort f) Radix sort g) Binary tree sort.
Write Java programs that use recursive and non-recursive
4. functions to traverse the given binary tree in a) Preorder b)
Inorder c) Postorder.
Write Java programs for the implementation of bfs and dfs for
5.
a given graph.
Write a Java program to implement Dijkstra’s algorithm for
6.
Single source shortest path problem.
Write a Java program that implements Kruskal’s algorithm to
7.
generate minimum cost spanning tree.

Write a Java program to perform the following operations: a)

8.
Insertion into a B-tree b) Searching in a B-tree.
Write a Java program that implements KMP algorithm for
9.
pattern matching.

Faculty Signature
(Ms. Swapna Singh)
 PROGRAM: 1

OBJECTIVE: Write Java programs that use both recursive and non-recursive
functions for implementing the following searching methods: a) Linear search
b) Binary search.

Linear Search Program Using Recursion

public class Test {
public static int recSearch(int data[], int l, int r, int key) {
if (r < l)
return -1;
if (data[l] == key)
return l;
return recSearch(data, l+1, r, key);
}

public static void main(String args[]){

int[] data= {50,27,30,50,70,9,19};
int key = 9;

int index = recSearch(data, 0, data.length-1, key);

if (index != -1)
System.out.println("Element " + key + " is present at index " + index);
else
System.out.println("Element " + key + " is not present");
}
}

Output
9 is found at index: 5
Binary search Search Program Using Non Recursion
class GFG {
int binarySearch(int arr[], int x)
{
int l = 0, int r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
public static void main(String args[])
{
GFG ob = new GFG();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index "
+ result);
}
}

Output:
Element found at index 3

Binary Search Program Using Recursion

import java.util.*;

class GFG {
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l && l <= arr.length - 1) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
public static void main(String args[])
{
GFG ob = new GFG();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index "
+ result);
}
}

Output
Element is present at index 3
 PROGRAM 2
OBJECTIVE: Write a Java program to implement all the functions of a dictionary
(ADT) using Hashing.

import java.io.*;
import java.util.*;
class AddElementsToHashtable {
public static void main(String args[])
{
Hashtable<Integer, String> ht1 = new Hashtable<>();

Hashtable<Integer, String> ht2

= new Hashtable<Integer, String>();
ht1.put (“Lucky”, "Delhi");
ht1.put (“Davis”, "USA");
ht1.put (“Andrew”, "France");
System.out.println ("Mappings of ht1 : " + ht1);
}
}

Output
Mappings of ht1: {Lucky=Delhi, Davis=USA, Andrew=France}
 PROGRAM 3
OBJECTIVE: Write Java programs for implementing the following sorting
methods: a) Bubble sort b) Insertion sort c) Quick sort d) Merge sort e) Heap
sort f) Radix sort g) Binary tree sort.

a) Bubble Sort
public class BubbleSortExample {
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] ={3,60,35,2,45,320,5};
System.out.println("Array Before Bubble Sort");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
 for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}

Output:
Array Before Bubble Sort
3 60 35 2 45 320 5
Array After Bubble Sort
2 3 5 35 45 60 320

b) Insertion Sort
class InsertionSort {
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
static void printArray(int arr[])
{
int n = arr.length;
 for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");

System.out.println();
}
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6 };

InsertionSort ob = new InsertionSort();

ob.sort(arr);

printArray(arr);
}
}

Output:

5 6 11 12 13

c) Quick Sort
import java.io.*;
class GFG{
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int low, int high)
{
 int pivot = arr[high];
int i = (low - 1);

for(int j = low; j <= high - 1; j++)

{

if (arr[j] < pivot)

{
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
static void quickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
static void printArray(int[] arr, int size)
{
for(int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}

Output
Sorted array:
1 5 7 8 9 10

d) Merge sort
class MergeSort
{
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
 if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m =l+ (r-l)/2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
 }
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted array");
printArray(arr);
}
}

Output
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13

e) Heap Sort
public class HeapSort {
public void sort(int arr[])
{
int n = arr.length;
 // Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

 if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

public static void main(String args[])

{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = arr.length;

HeapSort ob = new HeapSort();

ob.sort(arr);

System.out.println("Sorted array is");

printArray(arr);
}
}

Output
Sorted array is
5 6 7 11 12 13

f) Radix Sort
import java.io.*;
import java.util.*;
class Radix {
static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

static void countSort(int arr[], int n, int exp)

{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count, 0);
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
 count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
static void radixsort(int arr[], int n)
{
int m = getMax(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
static void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args)
{
int arr[] = { 573, 25, 415, 12, 161, 6 };
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}

Output
6 12 25 161 415 573
 g) Binary Tree Sort
class GFG
{
class Node
{
int key;
Node left, right;

public Node(int item)

{
key = item;
left = right = null;
}
}
Node root;
GFG()
{
root = null;
}
void insert(int key)
{
root = insertRec(root, key);
}
Node insertRec(Node root, int key)
{
if (root == null)
{
root = new Node(key);
return root;
}
 if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}

void inorderRec(Node root)

{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
void treeins(int arr[])
{
for(int i = 0; i < arr.length; i++)
{
insert(arr[i]);
}

}
public static void main(String[] args)
{
GFG tree = new GFG();
int arr[] = {5, 4, 7, 2, 11};
tree.treeins(arr);
tree.inorderRec(tree.root);
 }
}

Output:

2 4 5 7 11
 PROGRAM 4
OBJECTIVE: Write Java programs that use recursive and non-recursive
functions to traverse the given binary tree in a) Preorder b) Inorder c)
Postorder.

class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() { root = null; }
"bottom-up" postorder traversal. */
void printPostorder(Node node)
{
if (node == null)
return;
printPostorder(node.left);
printPostorder(node.right);
System.out.print(node.key + " ");
}
void printInorder(Node node)
{
if (node == null)
return;
 printInorder(node.left);
System.out.print(node.key + " ");
printInorder(node.right);
}
void printPreorder(Node node)
{
if (node == null)
return;
System.out.print(node.key + " ");
printPreorder(node.left);
printPreorder(node.right);
}
void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println(
"Preorder traversal of binary tree is ");
tree.printPreorder();
System.out.println(
tree.printInorder();
System.out.println(
 tree.printPostorder();
}
}

Output:
Preorder traversal of binary tree is
12453
Inorder traversal of binary tree is
42513
Postorder traversal of binary tree is
45231
 PROGRAM 5
OBJECTIVE: Write Java programs for the implementation of bfs and dfs for a
given graph.
Implementation of BFS
import java.io.*;
import java.util.*;
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency Lists
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v,int w)
{
adj[v].add(w);
}
void BFS(int s)
{
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
visited[s]=true;
queue.add(s);
while (queue.size() != 0)
{
s = queue.poll();
 System.out.print(s+" ");
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[])
{
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Breadth First Traversal "+
"(starting from vertex 2)");

g.BFS(2);
}
}
Output:
Following is Breadth First Traversal (starting from vertex 2)
2 0 3 1

Implementation of DFS
import java.io.*;
import java.util.*;
class Graph {
private int V; // No. of vertices
private LinkedList<Integer> adj[];
@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
}
void DFSUtil(int v, boolean visited[])
{
visited[v] = true;
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
void DFS(int v)
{
boolean visited[] = new boolean[V];
DFSUtil(v, visited);
}
public static void main(String args[])
{
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
 System.out.println(
"Following is Depth First Traversal "
+ "(starting from vertex 2)");
g.DFS(2);
}
}

Output:
Following is Depth First Traversal (starting from vertex 2)
2 0 1 3
 PROGRAM 6
OBJECTIVE: Write a Java program to implement Dijkstra’s algorithm for
Single source shortest path problem.
import java.util.*;
import java.io.*;
import java.lang.*;
public class DijkstraExample
{
static final int totalVertex = 9;
int minimumDistance(int distance[], Boolean spSet[])
{
int m = Integer.MAX_VALUE, m_index = -1;
for (int vx = 0; vx < totalVertex; vx++)
{
if (spSet[vx] == false && distance[vx] <= m)
{
m = distance[vx];
m_index = vx;
}
}
return m_index;

}
void printSolution(int distance[], int n)
{
System.out.println("The shortest Distance from source 0th node to all other nodes are: ");
for (int j = 0; j < n; j++)
System.out.println("To " + j + " the shortest distance is: " + distance[j]);
}
void dijkstra(int graph[][], int s)
{
int distance[] = new int[totalVertex]; // The output array distance[i] holds the shortest dista
nce from source s to j
Boolean spSet[] = new Boolean[totalVertex];
for (int j = 0; j < totalVertex; j++)
{
distance[j] = Integer.MAX_VALUE;
spSet[j] = false;
}
distance[s] = 0;
for (int cnt = 0; cnt < totalVertex - 1; cnt++)
{
int ux = minimumDistance(distance, spSet);
spSet[ux] = true;
for (int vx = 0; vx < totalVertex; vx++)
if (!spSet[vx] && graph[ux][vx] != -
1 && distance[ux] != Integer.MAX_VALUE && distance[ux] + graph[ux][vx] < distance[vx])
{
distance[vx] = distance[ux] + graph[ux][vx];
}
}
printSolution(distance, totalVertex);
}
public static void main(String argvs[])
{
int grph[][] = new int[][] { { -1, 3, -1, -1, -1, -1, -1, 7, -1 },
{ 3, -1, 7, -1, -1, -1, -1, 10, 4 },
{ -1, 7, -1, 6, -1, 2, -1, -1, 1 },
{ -1, -1, 6, -1, 8, 13, -1, -1, 3 },
{ -1, -1, -1, 8, -1, 9, -1, -1, -1 },
{ -1, -1, 2, 13, 9, -1, 4, -1, 5 },
 { -1, -1, -1, -1, -1, 4, -1, 2, 5 },
{ 7, 10, -1, -1, -1, -1, 2, -1, 6 },
{ -1, 4, 1, 3, -1, 5, 5, 6, -1 } };
DijkstraExample obj = new DijkstraExample();
obj.dijkstra(grph, 0);
}
}

Output:

The shortest Distance from source 0th node to all other nodes are:
To 0 the shortest distance is: 0
To 1 the shortest distance is: 3
To 2 the shortest distance is: 8
To 3 the shortest distance is: 10
To 4 the shortest distance is: 18
To 5 the shortest distance is: 10
To 6 the shortest distance is: 9
To 7 the shortest distance is: 7
To 8 the shortest distance is: 7
 PROGRAM 7
OBJECTIVE: Write a Java program that implements Kruskal’s algorithm to
generate minimum cost spanning tree
import Java.util.*;
class KruskalAlgorithm {
class Edge implements Comparable<Edge> {
int source, destination, weight;
public int compareTo(Edge edgeToCompare) {
return this.weight - edgeToCompare.weight;
}
};
class Subset {
int parent, value;
};
int vertices, edges;
Edge edgeArray[];
KruskalAlgorithm(int vertices, int edges) {
this.vertices = vertices;
this.edges = edges;
edgeArray = new Edge[this.edges];
for (int i = 0; i < edges; ++i)
edgeArray[i] = new Edge(); //create edge for all te edges given by the user
}
void applyKruskal() {
Edge finalResult[] = new Edge[vertices];
int newEdge = 0;
int index = 0;
for (index = 0; index < vertices; ++index)
finalResult[index] = new Edge();
Arrays.sort(edgeArray);
 Subset subsetArray[] = new Subset[vertices];
for (index = 0; index < vertices; ++index)
subsetArray[index] = new Subset();
for (int vertex = 0; vertex < vertices; ++vertex) {
subsetArray[vertex].parent = vertex;
subsetArray[vertex].value = 0;
}
index = 0;
while (newEdge < vertices - 1) {
Edge nextEdge = new Edge();
nextEdge = edgeArray[index++];
int nextSource = findSetOfElement(subsetArray, nextEdge.source);
int nextDestination = findSetOfElement(subsetArray, nextEdge.destination);
if (nextSource != nextDestination) {
finalResult[newEdge++] = nextEdge;
performUnion(subsetArray, nextSource, nextDestination);
}
}
for (index = 0; index < newEdge; ++index)
System.out.println(finalResult[index].source + " - " + finalResult[index].destination + "
: " + finalResult[index].weight);
}
int findSetOfElement(Subset subsetArray[], int i) {
if (subsetArray[i].parent != i)
subsetArray[i].parent = findSetOfElement(subsetArray, subsetArray[i].parent);
return subsetArray[i].parent;
}

void performUnion(Subset subsetArray[], int sourceRoot, int destinationRoot) {

int nextSourceRoot = findSetOfElement(subsetArray, sourceRoot);
 int nextDestinationRoot = findSetOfElement(subsetArray, destinationRoot);

if (subsetArray[nextSourceRoot].value < subsetArray[nextDestinationRoot].value)

subsetArray[nextSourceRoot].parent = nextDestinationRoot;
else if (subsetArray[nextSourceRoot].value > subsetArray[nextDestinationRoot].value)
subsetArray[nextDestinationRoot].parent = nextSourceRoot;
else {
subsetArray[nextDestinationRoot].parent = nextSourceRoot;
subsetArray[nextSourceRoot].value++;
}
}
public static void main(String[] args) {
int v, e;
Scanner sc = new Scanner(System.in);
System.out.println("Enter number of vertices: ");
v = sc.nextInt();
System.out.println("Enter number of edges");
e = sc.nextInt();
KruskalAlgorithm graph = new KruskalAlgorithm(v, e);
for(int i = 0; i < e; i++){
System.out.println("Enter source value for edge["+ i +"]");
graph.edgeArray[i].source = sc.nextInt();
System.out.println("Enter destination value for edge["+ i +"]");
graph.edgeArray[i].destination = sc.nextInt();
System.out.println("Enter weight for edge["+i+"]");
graph.edgeArray[i].weight = sc.nextInt();
}
graph.applyKruskal();
Output
 PROGRAM 8
OBJECTIVE: Write a Java program to perform the following operations: a)
Insertion into a B-tree b) Searching in a B-tree.
a) Insertion into a B-tree
public class BTree {
private int T;
public class Node {
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;
public int Find(int k) {
for (int i = 0; i < this.n; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}
public BTree(int t) {
T = t;
root = new Node();
root.n = 0;
root.leaf = true;
}
private Node root;
private void split(Node x, int pos, Node y) {
Node z = new Node();
z.leaf = y.leaf;
 z.n = T - 1;
for (int j = 0; j < T - 1; j++) {
z.key[j] = y.key[j + T];
}
if (!y.leaf) {
for (int j = 0; j < T; j++) {
z.child[j] = y.child[j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= pos + 1; j--) {
x.child[j + 1] = x.child[j];
}
x.child[pos + 1] = z;
for (int j = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}
public void insert(final int key) {
Node r = root;
if (r.n == 2 * T - 1) {
Node s = new Node();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
split(s, 0, r);
_insert(s, key);
 } else {
_insert(r, key);
}
}
final private void _insert(Node x, int k) {
if (x.leaf) {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
x.key[i + 1] = x.key[i];
}
x.key[i + 1] = k;
x.n = x.n + 1;
} else {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
};
i++;
Node tmp = x.child[i];
if (tmp.n == 2 * T - 1) {
split(x, i, tmp);
if (k > x.key[i]) {
i++;
}
}
_insert(x.child[i], k);
}

}
public void display() {
display(root);
 }
private void display(Node x) {
assert (x == null);
for (int i = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
}
if (!x.leaf) {
for (int i = 0; i < x.n + 1; i++) {
display(x.child[i]);
}
}
}
public static void main(String[] args) {
BTree b = new BTree(3);
b.insert(8);
b.insert(9);
b.insert(10);
b.insert(11);
b.insert(15);
b.insert(20);
b.insert(17);
b.display();
}
}

OUTPUT
 PROGRAM 9
OBJECTIVE: Write a Java program that implements KMP algorithm for
pattern matching.
class KMP_String_Matching {
void KMPSearch(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
int lps[] = new int[M];
int j = 0; // index for pat[]
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
}
if (j == M) {
System.out.println("Found pattern "
+ "at index " + (i - j));
j = lps[j - 1];
}
else if (i < N && pat.charAt(j) != txt.charAt(i)) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(String pat, int M, int lps[])
{
int len = 0;
int i = 1;
lps[0] = 0; // lps[0] is always 0
while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
len = lps[len - 1];
}
else // if (len == 0)
{
lps[i] = len;
i++;
}
}
}
}
public static void main(String args[])
{
String txt = "ABABDABACDABABCABAB";
String pat = "ABABCABAB";
new KMP_String_Matching().KMPSearch(pat, txt);
}
}

Output:
Found pattern at index 10