S.

NO
. EXPERIMENT PAGE
Write Java programs that use both recursive and non-recursive functions for
implementing the following searching methods: a) Linear search b) Binary
1 search 2-3
Write a Java program to implement all the functions of a dictionary (ADT)
using hashing.
2 4
Write a Java program to implement Dijkstra’s algorithm for Single source
shortest path problem.
3 5-6
Write Java programs that use recursive and non-recursive functions to traverse
the given binary tree in a) Preorder b) Inorder c) Postorder.
4 7-9

Write Java programs for the implementation of bfs and dfs for a given graph.
5 10-11
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)
6 Binary tree sort 12-17
Write a Java program to perform the following operations: a) Insertion into a B-
tree b) Searching in a B-tree
7 18-21
Write a Java program that implements Kruskal’s algorithm to generate
minimum cost spanning tree.
8 22-24

Write a Java program that implements KMP algorithm for pattern matching.
9 25-26

1
Experiment 1: Linear and Binary Search (Recursive and Non-Recursive)
Objective: To implement recursive and non-recursive functions for Linear Search and
Binary Search.
Program:
import java.util.*;
class Experiment1
{
// Non-recursive Linear Search
public static int linearSearch(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key)
return i;
}
return -1;
}
// Recursive Linear Search
public static int linearSearchRec(int[] arr, int key, int index) {
if (index >= arr.length)
return -1;
if (arr[index] == key)
return index;
return linearSearchRec(arr, key, index + 1);
}
// Non-recursive Binary Search
public static int binarySearch(int[] arr, int key) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
// Recursive Binary Search
public static int binarySearchRec(int[] arr, int key, int low, int high) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
return binarySearchRec(arr, key, mid + 1, high);
else
return binarySearchRec(arr, key, low, mid - 1);
}
public static void main(String[] args) {

2
 int[] arr = {2, 4, 6, 8, 10, 12, 14};
int key = 10;

System.out.println("Non-Recursive Linear Search: " + linearSearch(arr, key));

System.out.println("Recursive Linear Search: " + linearSearchRec(arr, key, 0));
Arrays.sort(arr); // Ensure array is sorted
System.out.println("Non-Recursive Binary Search: " + binarySearch(arr, key));
System.out.println("Recursive Binary Search: " + binarySearchRec(arr, key, 0,
arr.length - 1));
}
}

3
Experiment 2: Dictionary using Hashing
Objective: To implement all the functions of a dictionary (ADT) using Hashing.
Program:
import java.util.HashMap;
class Experiment2 {
public static void main(String[] args) {
HashMap<String, String> dictionary = new HashMap<>();
// Insert
dictionary.put("Java", "A high-level programming language.");
dictionary.put("Python", "An interpreted high-level programming language.");
// Search
String word = "Java";
if (dictionary.containsKey(word)) {
System.out.println(word + ": " + dictionary.get(word));
} else {
System.out.println(word + " not found in dictionary.");
}
// Delete
dictionary.remove("Python");
// Display all
for (Map.Entry<String, String> entry : dictionary.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}

4
Experiment 3: Dijkstra’s Algorithm
Objective: To implement Dijkstra’s algorithm to find the shortest path from a single
source vertex to all other vertices in a given weighted graph.
Program:
import java.util.*;

public class DijkstraAlgorithm {

static final int INF = Integer.MAX_VALUE;

public static void dijkstra(int[][] graph, int src) {

int V = graph.length;
int[] dist = new int[V]; // Output array. dist[i] will hold the shortest distance from
src to i
boolean[] visited = new boolean[V]; // visited[i] will true if vertex i is included in
shortest path tree

// Initialize distances as INFINITE and visited[] as false

Arrays.fill(dist, INF);
dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

// Pick the minimum distance vertex from the set of vertices not yet processed
int u = minDistance(dist, visited);
visited[u] = true;

// Update dist value of the adjacent vertices of the picked vertex

for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] != 0 &&
dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

printSolution(dist, src);
}

// A utility function to find the vertex with minimum distance value

static int minDistance(int[] dist, boolean[] visited) {
int min = INF, min_index = -1;
for (int v = 0; v < dist.length; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

5
 // A utility function to print the constructed distance array
static void printSolution(int[] dist, int src) {
System.out.println("Vertex\tDistance from Source " + src);
for (int i = 0; i < dist.length; i++)
System.out.println(i + "\t\t" + dist[i]);
}

// Main method
public static void main(String[] args) {
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};

dijkstra(graph, 0); // Source vertex = 0

}
}

6
Experiment 4: Binary Tree Traversal (Recursive and Non-Recursive)
Objective: To write Java programs that use both recursive and non-recursive methods
to traverse a given binary tree in: a) Preorder b) Inorder c) Postorder
Program:
import java.util.*;

// Node class
class TreeNode {
int data;
TreeNode left, right;

TreeNode(int item) {
data = item;
left = right = null;
}
}

public class BinaryTreeTraversal {

TreeNode root;

// ---------- Recursive Traversals ----------

void inorderRecursive(TreeNode node) {
if (node == null)
return;
inorderRecursive(node.left);
System.out.print(node.data + " ");
inorderRecursive(node.right);
}

void preorderRecursive(TreeNode node) {

if (node == null)
return;
System.out.print(node.data + " ");
preorderRecursive(node.left);
preorderRecursive(node.right);
}

void postorderRecursive(TreeNode node) {

if (node == null)
return;
postorderRecursive(node.left);
postorderRecursive(node.right);
System.out.print(node.data + " ");
}

// ---------- Non-Recursive Traversals ----------

void inorderNonRecursive(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = node;

7
 while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}

current = stack.pop();
System.out.print(current.data + " ");
current = current.right;
}
}

void preorderNonRecursive(TreeNode node) {

if (node == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(node);

while (!stack.isEmpty()) {
TreeNode temp = stack.pop();
System.out.print(temp.data + " ");

if (temp.right != null)
stack.push(temp.right);
if (temp.left != null)
stack.push(temp.left);
}
}

void postorderNonRecursive(TreeNode node) {

Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();

if (node == null) return;

stack1.push(node);
while (!stack1.isEmpty()) {
TreeNode temp = stack1.pop();
stack2.push(temp);

if (temp.left != null)
stack1.push(temp.left);
if (temp.right != null)
stack1.push(temp.right);
}

while (!stack2.isEmpty()) {
System.out.print(stack2.pop().data + " ");
}
}

8
 public static void main(String[] args) {
BinaryTreeTraversal tree = new BinaryTreeTraversal();

tree.root = new TreeNode(1);

tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(7);

System.out.println(\"Recursive Inorder:\");
tree.inorderRecursive(tree.root);
System.out.println(\"\\nNon-Recursive Inorder:\");
tree.inorderNonRecursive(tree.root);

System.out.println(\"\\n\\nRecursive Preorder:\");
tree.preorderRecursive(tree.root);
System.out.println(\"\\nNon-Recursive Preorder:\");
tree.preorderNonRecursive(tree.root);

System.out.println(\"\\n\\nRecursive Postorder:\");
tree.postorderRecursive(tree.root);
System.out.println(\"\\nNon-Recursive Postorder:\");
tree.postorderNonRecursive(tree.root);
}
}

9
Experiment 5: BFS and DFS for a Graph
Objective:
To implement Breadth-First Search (BFS) and Depth-First Search (DFS) traversal
algorithms for a given graph using Java.
Program:
import java.util.*;

public class GraphTraversal {

private int vertices; // Number of vertices

private LinkedList<Integer>[] adjList; // Adjacency List

// Constructor
public GraphTraversal(int v) {
vertices = v;
adjList = new LinkedList[v];
for (int i = 0; i < v; i++) {
adjList[i] = new LinkedList<>();
}
}

// Add edge to the graph

void addEdge(int v, int w) {
adjList[v].add(w); // Directed graph
// For undirected graph, use: adjList[v].add(w); adjList[w].add(v);
}

// ----------- BFS Implementation -----------

void BFS(int start) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();

visited[start] = true;
queue.add(start);

System.out.print("BFS Traversal: ");

while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");

for (int neighbor : adjList[node]) {

if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}

10
 // ----------- DFS Implementation -----------
void DFSUtil(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");

for (int neighbor : adjList[node]) {

if (!visited[neighbor])
DFSUtil(neighbor, visited);
}
}

void DFS(int start) {

boolean[] visited = new boolean[vertices];
System.out.print("DFS Traversal: ");
DFSUtil(start, visited);
System.out.println();
}

// ----------- Main Method -----------

public static void main(String[] args) {
GraphTraversal graph = new GraphTraversal(6);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);

graph.BFS(0); // Starting BFS from node 0

graph.DFS(0); // Starting DFS from node 0
}
}

11
Experiment 6: Sorting Algorithms
Objective: To implement various sorting algorithms in Java.
a) Bubble Sort
import java.util.Arrays;

class BubbleSort {
// Bubble Sort
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped)
break;
}
}

public static void main(String[] args) {

int[] arr = {64, 25, 12, 22, 11};
bubbleSort(arr);
System.out.println("Sorted array (Bubble Sort): " + Arrays.toString(arr));
}
}
b) Insertion Sort
import java.util.Arrays;

class InsertionSort {
// Insertion Sort
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

12
 public static void main(String[] args) {
int[] arr = {9, 5, 1, 4, 3};
insertionSort(arr);
System.out.println("Sorted array (Insertion Sort): " + Arrays.toString(arr));
}
}
c) Quick Sort
import java.util.*;

class QuickSort {
public 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);
}
}

public static int partition(int[] arr, int low, int high) {

int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

public static void main(String[] args) {

int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using Quick Sort: " + Arrays.toString(arr));
}
}
d) Merge Sort
import java.util.*;

class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

13
 merge(arr, left, mid, right);
}
}

public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
System.arraycopy(arr, left, L, 0, n1);
System.arraycopy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}

public static void main(String[] args) {

int[] arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using Merge Sort: " + Arrays.toString(arr));
}
}
e) Heap Sort
import java.util.*;

class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i > 0; i--) {

int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

public static void heapify(int[] arr, int n, int i) {

14
 int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

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

largest = l;

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

largest = r;

if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

heapify(arr, n, largest);
}
}

public static void main(String[] args) {

int[] arr = {4, 10, 3, 5, 1};
heapSort(arr);
System.out.println("Sorted array using Heap Sort: " + Arrays.toString(arr));
}
}
f) Radix Sort
import java.util.*;

class RadixSort {
public static void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, exp);
}

public static int getMax(int[] arr) {

int max = arr[0];
for (int i : arr)
if (i > max)
max = i;
return max;
}

public static void countSort(int[] arr, int exp) {

int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
Arrays.fill(count, 0);

for (int i : arr)

15
 count[(i / exp) % 10]++;

for (int i = 1; i < 10; i++)

count[i] += count[i - 1];

for (int i = n - 1; i >= 0; i--) {

int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}

System.arraycopy(output, 0, arr, 0, n);

}

public static void main(String[] args) {

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
System.out.println("Sorted array using Radix Sort: " + Arrays.toString(arr));
}
}
g) Binary Tree Sort
import java.util.*;

class TreeNode {
int val;
TreeNode left, right;

TreeNode(int item) {
val = item;
left = right = null;
}
}

class BinaryTreeSort {
TreeNode root;

void insert(int key) {

root = insertRec(root, key);
}

TreeNode insertRec(TreeNode root, int key) {

if (root == null) {
root = new TreeNode(key);
return root;
}
if (key < root.val)
root.left = insertRec(root.left, key);
else
root.right = insertRec(root.right, key);

16
 return root;
}

void inorder(TreeNode root, List<Integer> result) {

if (root != null) {
inorder(root.left, result);
result.add(root.val);
inorder(root.right, result);
}
}

public static void main(String[] args) {

int[] arr = {5, 2, 1, 3, 4};
BinaryTreeSort tree = new BinaryTreeSort();
for (int val : arr)
tree.insert(val);

List<Integer> sorted = new ArrayList<>();

tree.inorder(tree.root, sorted);
System.out.println("Sorted array using Binary Tree Sort: " + sorted);
}
}

17
Experiment 7: B-Tree Operations
Objective: To implement insertion and search operations in a B-tree.
Program:
// BTreeNode class
class BTreeNode {
int[] keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode[] children; // An array of child pointers
int n; // Current number of keys
boolean leaf; // Is true when node is leaf. Otherwise false

BTreeNode(int t, boolean leaf) {

this.t = t;
this.leaf = leaf;
this.keys = new int[2 * t - 1];
this.children = new BTreeNode[2 * t];
this.n = 0;
}

// A function to traverse all nodes in a subtree rooted with this node

void traverse() {
int i;
for (i = 0; i < this.n; i++) {
if (!leaf) {
children[i].traverse();
}
System.out.print(keys[i] + " ");
}

if (!leaf) {
children[i].traverse();
}
}

// A function to search a key in the subtree rooted with this node

BTreeNode search(int key) {
int i = 0;
while (i < n && key > keys[i]) {
i++;
}

if (i < n && keys[i] == key) {

return this;
}

if (leaf) {
return null;
}

return children[i].search(key);

18
}

// Insert a new key in the subtree rooted with this node (assuming this node is not full)
void insertNonFull(int key) {
int i = n - 1;

if (leaf) {
// Move keys greater than key forward
while (i >= 0 && keys[i] > key) {
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = key;
n = n + 1;
} else {
while (i >= 0 && keys[i] > key) {
i--;
}

if (children[i + 1].n == 2 * t - 1) {
splitChild(i + 1, children[i + 1]);

if (keys[i + 1] < key) {

i++;
}
}
children[i + 1].insertNonFull(key);
}
}

// Split the child y of this node. i is index of y in child array children[]

void splitChild(int i, BTreeNode y) {
BTreeNode z = new BTreeNode(y.t, y.leaf);
z.n = t - 1;

for (int j = 0; j < t - 1; j++) {

z.keys[j] = y.keys[j + t];
}

if (!y.leaf) {
for (int j = 0; j < t; j++) {
z.children[j] = y.children[j + t];
}
}

y.n = t - 1;

for (int j = n; j >= i + 1; j--) {

children[j + 1] = children[j];

19
 }

children[i + 1] = z;

for (int j = n - 1; j >= i; j--) {

keys[j + 1] = keys[j];
}

keys[i] = y.keys[t - 1];

n = n + 1;
}
}

// BTree class
class BTree {
BTreeNode root;
int t; // Minimum degree

BTree(int t) {
this.root = null;
this.t = t;
}

// Function to traverse the tree

void traverse() {
if (root != null) {
root.traverse();
}
}

// Function to search a key

BTreeNode search(int key) {
if (root == null) return null;
return root.search(key);
}

// Insertion function
void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
root.keys[0] = key;
root.n = 1;
} else {
if (root.n == 2 * t - 1) {
BTreeNode s = new BTreeNode(t, false);
s.children[0] = root;
s.splitChild(0, root);
int i = 0;
if (s.keys[0] < key) {
i++;

20
 }
s.children[i].insertNonFull(key);
root = s;
} else {
root.insertNonFull(key);
}
}
}
}

// Driver class
public class BTreeDemo {
public static void main(String[] args) {
BTree t = new BTree(3); // A B-Tree with minimum degree 3

int[] keys = {10, 20, 5, 6, 12, 30, 7, 17};

for (int key : keys) {
t.insert(key);
}

System.out.println("Traversal of the constructed tree is:");

t.traverse();

int k = 6;
if (t.search(k) != null)
System.out.println("\n\nPresent");
else
System.out.println("\n\nNot Present");
}
}

21
Experiment 8: Write a Java program that implements Kruskal’s algorithm to generate
minimum cost spanning tree.
Objective: To implement graph algorithms for Minimum cost Spanning tree.
Program:
import java.util.*;

// Class to represent an edge in the graph

class Edge implements Comparable<Edge> {
int src, dest, weight;

Edge(int src, int dest, int weight) {

this.src = src;
this.dest = dest;
this.weight = weight;
}

// Used for sorting edges by weight

public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}

// Disjoint Set (Union-Find) class

class DisjointSet {
int[] parent, rank;

DisjointSet(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
parent[i] = i;
}

// Find root of set containing node

int find(int i) {
if (parent[i] != i)
parent[i] = find(parent[i]); // Path compression
return parent[i];
}

// Union of two sets

void union(int x, int y) {
int xroot = find(x);
int yroot = find(y);

if (rank[xroot] < rank[yroot]) {

parent[xroot] = yroot;
} else if (rank[xroot] > rank[yroot]) {
parent[yroot] = xroot;
} else {

22
 parent[yroot] = xroot;
rank[xroot]++;
}
}
}

// Main Graph class implementing Kruskal's Algorithm

public class KruskalMST {
int V, E; // Number of vertices and edges
Edge[] edges;

KruskalMST(int v, int e) {
V = v;
E = e;
edges = new Edge[E];
}

void kruskalMST() {
// Step 1: Sort edges by increasing weight
Arrays.sort(edges);

// Disjoint set for tracking connected components

DisjointSet ds = new DisjointSet(V);

Edge[] result = new Edge[V - 1]; // MST will have V-1 edges
int e = 0, i = 0; // Index for result[] and sorted edges

while (e < V - 1 && i < E) {

Edge next = edges[i++];

int x = ds.find(next.src);
int y = ds.find(next.dest);

// If including this edge doesn't cause cycle

if (x != y) {
result[e++] = next;
ds.union(x, y);
}
}

// Print the MST

System.out.println("Edges in the Minimum Spanning Tree:");
int minCost = 0;
for (i = 0; i < e; ++i) {
System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
minCost += result[i].weight;
}
System.out.println("Minimum Cost = " + minCost);
}

23
 // Driver method
public static void main(String[] args) {

int V = 4; // Number of vertices

int E = 5; // Number of edges
KruskalMST graph = new KruskalMST(V, E);

// Add edges
graph.edges[0] = new Edge(0, 1, 10);
graph.edges[1] = new Edge(0, 2, 6);
graph.edges[2] = new Edge(0, 3, 5);
graph.edges[3] = new Edge(1, 3, 15);
graph.edges[4] = new Edge(2, 3, 4);

// Run Kruskal's algorithm

graph.kruskalMST();
}
}

24
Experiment 9: Write a Java program that implements KMP algorithm for pattern
matching.
Objective: To implement KMP algorithm.
Program:
public class KMPAlgorithm {

// Method to compute LPS (Longest Prefix Suffix) array

void computeLPSArray(String pattern, int[] lps) {
int length = 0; // length of the previous longest prefix suffix
int i = 1;
lps[0] = 0; // LPS[0] is always 0

while (i < pattern.length()) {

if (pattern.charAt(i) == pattern.charAt(length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1]; // fallback
} else {
lps[i] = 0;
i++;
}
}
}
}

// KMP Search algorithm

void KMPSearch(String pattern, String text) {
int M = pattern.length();
int N = text.length();

// Create lps[] for the pattern

int[] lps = new int[M];
computeLPSArray(pattern, lps);

int i = 0; // index for text[]

int j = 0; // index for pattern[]

while (i < N) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}

if (j == M) {
System.out.println("Pattern found at index " + (i - j));
j = lps[j - 1]; // continue searching
} else if (i < N && pattern.charAt(j) != text.charAt(i)) {

25
 if (j != 0) {
j = lps[j - 1]; // use LPS to skip characters
} else {
i++;
}
}
}
}

// Driver method
public static void main(String[] args) {
KMPAlgorithm kmp = new KMPAlgorithm();

String text = "ABABDABACDABABCABAB";

String pattern = "ABABCABAB";

System.out.println("Text: " + text);

System.out.println("Pattern: " + pattern);

kmp.KMPSearch(pattern, text);
}
}

26