// Question 1.

Write a program to sort the elements of an array using Randomized

Quick Sort (the program should report the number of comparisons).
[INCREASING ORDER]

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;

int comparison_count = 0;

int partition(int *a, int p, int q){

int x = a[p]; N
int i=p;
for(int j=p+1;j<=q;j++){
comparison_count++; // Increment the comparison count for each comparison
made
if(a[j]<=x){
i++;
swap(a[i],a[j]);
};
}
swap(a[i],a[p]); //we are swapping the elements at index i and that of index
p. NOT the index
return i; //Now the pivot will be at index i, which before was at
index p
}

int random_generator(int p, int q){

return p + rand()%(q-p+1);
}

void randomised_quicksort(int *a, int p, int q){

if(p<q){
int r=random_generator(p,q);
cout << "Randomly chosen pivot: " << a[r] << endl;
swap(a[p],a[r]);
int m=partition(a,p,q);
randomised_quicksort(a,p,m-1);
randomised_quicksort(a,m+1,q);
}
}

int main(){
srand(time(NULL)); // This will call srand only once in the beginning

int size;
cout<<"Enter the size of array"<<endl;
cin>>size;
int *a= new int[size];
cout<<"Enter the array "<<endl;
for(int i = 0; i < size; i++){
cin >> a[i];
}

randomised_quicksort(a,0,size-1); //If we entered array of size 5, so the index

will be of 4, as it starts with 0
cout<<"Sorted array : ";
for(int i=0; i<size; i++){
 cout<<a[i]<<" ";
}
cout<<endl;

cout << "Number of comparisons: " << comparison_count << endl;

delete[] a; // Deallocate memory
return 0;
}

// Question 1. Write a program to sort the elements of an array using Randomized

Quick Sort (the program should report the number of comparisons).
[DECREASING ORDER]

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;

int comparison_count = 0;

int partition(int *a, int p, int q) {

int x = a[p];
int i = p;
for(int j = p+1; j <= q; j++) {
comparison_count++; // Increment the comparison count for each comparison
made
if(a[j] >= x) { // Changed from <= to >=
i++;
swap(a[i], a[j]);
}
}
swap(a[i], a[p]); // Swap the pivot to its correct position
return i; // Return the partition index
}

int random_generator(int p, int q) {

return p + rand() % (q - p + 1);
}

void randomised_quicksort(int *a, int p, int q) {

if(p < q) {
int r = random_generator(p, q);
cout << "Randomly chosen pivot: " << a[r] << endl;
swap(a[p], a[r]);
int m = partition(a, p, q);
randomised_quicksort(a, p, m-1);
randomised_quicksort(a, m+1, q);
}
}

int main() {
srand(time(NULL)); // Seed the random number generator
int size;
cout << "Enter the size of array: ";
cin >> size;
 int *a = new int[size];

cout << "Enter the array elements: " << endl;

for(int i = 0; i < size; i++) {
cin >> a[i];
}

randomised_quicksort(a, 0, size-1);

cout << "Array sorted in decreasing order: ";

for(int i = 0; i < size; i++) {
cout << a[i] << " ";
}
cout << endl;

cout << "Number of comparisons: " << comparison_count << endl;

delete[] a; // Deallocate memory

return 0;
}

// Question 2. Write a program to find the ith smallest element of an array using
Randomized Select.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

// Swap function to replace the missing swap

void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

int partition(int *a, int p, int q) {

int x = a[p];
int i = p;
for (int j = p + 1; j <= q; j++) {
if (a[j] <= x) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i], a[p]);
return i;
}

int random_generator(int p, int q) {

return p + rand() % (q - p + 1);
}

int randomised_select(int *a, int p, int q, int i) {

// Base case: if there's only one element
 if (p == q) {
return a[p];
}

int r = random_generator(p, q); // Generate a random index

swap(a[p], a[r]); // Swap the first element with the random
element

int m = partition(a, p, q); // Partition the array and get pivot index

int k = m - p + 1; // Rank of the pivot element

if (i == k) {
return a[m]; // Found the ith smallest element
}
else if (i < k) {
return randomised_select(a, p, m - 1, i); // Search in the left subarray
}
else {
return randomised_select(a, m + 1, q, i - k); // Search in the right
subarray
}
}

int main() {
srand(time(NULL));

int size, i;
cout << "Enter the size of the array: ";
cin >> size;

int* a = new int[size];

cout << "Enter the elements of the array: ";

for (int j = 0; j < size; j++) {
cin >> a[j];
}

cout << "Enter the value of i (for the ith smallest element): ";
cin >> i;

// Find and print the ith smallest element

int result = randomised_select(a, 0, size - 1, i);
cout << "The " << i << "th smallest element is: " << result << endl;

delete[] a;
return 0;
}

// Question 3. Write a program to determine the minimum spanning tree of a graph

using Kruskal’s algorithm.

#include <iostream>
#include <vector>
using namespace std;

struct UnionNode {
int data;
UnionNode* parent;
int size;

UnionNode(int ele){
data = ele;
parent = this;
size = 1;
}
};

class UnionFind {
std::vector<UnionNode*> pointersVector;

public:
void makeUnionFind(int vertices) {
for (int i = 0; i < vertices; i++) {
pointersVector.push_back(new UnionNode(i));
}
}

int find(int val) {

UnionNode* node = pointersVector[val];
if (node->parent != node) {
node->parent = pointersVector[find(node->parent->data)];
}
return node->parent->data;
}

void Union(int s1, int s2) {

UnionNode* root1 = pointersVector[find(s1)];
UnionNode* root2 = pointersVector[find(s2)];

if (root1 != root2) {
if (root1->size < root2->size) {
root1->parent = root2;
root2->size += root1->size;
} else {
root2->parent = root1;
root1->size += root2->size;
}
}
}

void display() {
for (int i = 0; i < pointersVector.size(); i++) {
cout << i << " : " << find(i) << endl;
}
}

~UnionFind() {
for (auto node : pointersVector) {
delete node;
}
}
};
struct Node{
int source;
int destination;
int weight;
Node * next;
Node(int Source,int Destination,int Weight){
destination= Destination;
weight = Weight;
source = Source;
next=NULL;
}
};

class LinkedList{
Node * head;
public:
LinkedList(){
head=NULL;
}
Node * getHeadNode(){return head;}
bool isEmpty(){return head==NULL;}
void addToHead(int source,int destination,int weight);
Node * search(int ele);
void display();
};

void LinkedList::addToHead(int source,int destination,int weight){

Node * n = new Node(source,destination,weight);
if(isEmpty()){
head = n;
}
else{
n->next=head;
head = n;
}
}

Node * LinkedList::search(int ele){

Node * temp =head;
while(temp!=NULL){
if(temp->source==ele)
return temp;
temp=temp->next;
}
return NULL;
}

void LinkedList::display(){
cout<<"[";
Node * temp = head;
while(temp!=NULL){
cout<<"{"<<temp->source<<" ,"<<temp->destination<<","<<temp->weight<<"},";
temp=temp->next;
}
cout<<"\b]\n";
}
class Graph{
int vertex;
LinkedList * adjList;
public:
Graph(int n){
vertex = n;
adjList = new LinkedList[vertex];
}
void addEdge(int u,int v,int weight);
void display();
void kruskal();
};

void Graph::addEdge(int u,int v,int weight){

if(adjList[u].search(v)==NULL)
adjList[u].addToHead(u,v,weight);

if(adjList[v].search(u)==NULL)
adjList[v].addToHead(v,u,weight);
}

void Graph::display(){
for (int i = 0; i < vertex; i++)
{
cout<<"List of vertex "<<i<<": ";
adjList[i].display();
}
}
void Graph::kruskal() {
std::vector<Node*> edges;

for (int i = 0; i < vertex; i++) {

Node* temp = adjList[i].getHeadNode();
while (temp != NULL) {
edges.push_back(temp);
temp = temp->next;
}
}

for (int i = 1; i < edges.size(); i++) {

Node* key = edges[i];
int j = i - 1;
while (j >= 0 && edges[j]->weight > key->weight) {
edges[j + 1] = edges[j];
j = j - 1;
}
edges[j + 1] = key;
}

UnionFind uf;
uf.makeUnionFind(vertex);

int mstWeight = 0;
cout << "MST: [";
for (auto edge : edges) {
if (uf.find(edge->source) != uf.find(edge->destination)) {
 mstWeight += edge->weight;
cout << "\n\t{" << edge->source << "," << edge->destination << "," <<
edge->weight << "}";
uf.Union(edge->source, edge->destination);
}
}
cout << "\n]";
cout << "\nMinimum Cost: " << mstWeight;
}

int main(){
cout<<"Enter Number of vertex in the Graph:\n";
int n;
cin>>n;

Graph A(n);

while(true){
int u,v,weight;
cout<<"\nEnter 1 to addEdge\n"
<<"Enter 2 to display graph\n"
<<"Enter 3 to find mst using Kruskal\n"
<<"Enter 4 to exit\n"
<<"enter choice:";
int ch;
cin>>ch;
switch (ch)
{
case 1:
cout<<"\nEnter edge u and v and weight : ";
cin>>u>>v>>weight;
if((u<n && u>=0) && (v<n && v>=0)){
A.addEdge(u,v,weight);}
break;
case 2:
A.display();
break;
case 3:
A.kruskal();
break;
case 4:
exit(0);
default:
break;
}
}
}

// Question 4. Write a program to implement the Bellman-Ford algorithm to find the

shortest paths
from a given source node to all other nodes in a graph.

#include <iostream>
#include <climits>
using namespace std;

struct Node {
int data;
int weight;
Node* next;
Node(int ele, int Weight) {
data = ele;
weight = Weight;
next = NULL;
}
};

class LinkedList {
Node* head;
public:
LinkedList() { head = NULL; }
void addToHead(int ele, int weight);
Node* search(int ele);
void display();
bool isEmpty() { return head == NULL; }
Node* getHeadNode() { return head; }
};

void LinkedList::addToHead(int ele, int weight) {

Node* n = new Node(ele, weight);
if (isEmpty()) {
head = n;
} else {
n->next = head;
head = n;
}
}

Node* LinkedList::search(int ele) {

Node* temp = head;
while (temp != NULL) {
if (temp->data == ele)
return temp;
temp = temp->next;
}
return NULL;
}

void LinkedList::display() {
cout << "[ ";
Node* temp = head;
while (temp != NULL) {
cout << "{v:" << temp->data << ",w:" << temp->weight << "} ,";
temp = temp->next;
}
cout << "\b ]\n";
}

class DirectedGraph {
int vertex;
LinkedList* adjList;
public:
 DirectedGraph(int n) {
vertex = n;
adjList = new LinkedList[vertex];
}
~DirectedGraph() { delete[] adjList; }
void addEdge(int u, int v, int weight);
int bellmanFord(int source, int destination);
void display();
};

void DirectedGraph::addEdge(int u, int v, int weight) {

if (adjList[u].search(v) == NULL)
adjList[u].addToHead(v, weight);
}

int DirectedGraph::bellmanFord(int source, int destination) {

// Distance array to store shortest distances
int* dist = new int[vertex];

// Initialize distances
for (int i = 0; i < vertex; i++) {
dist[i] = INT_MAX;
}
dist[source] = 0;

// Relaxation step: Iterate vertex-1 times

for (int k = 0; k < vertex - 1; k++) {
bool updated = false;

// Check all vertices and their adjacent edges

for (int u = 0; u < vertex; u++) {
Node* current = adjList[u].getHeadNode();

while (current != NULL) {

int v = current->data;
int weight = current->weight;

// Relaxation condition
if (dist[u] != INT_MAX &&
dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
updated = true;
}

current = current->next;
}
}

// If no updates in an iteration, we can break early

if (!updated) break;
}

// Check for negative weight cycles

for (int u = 0; u < vertex; u++) {
Node* current = adjList[u].getHeadNode();

while (current != NULL) {

int v = current->data;
int weight = current->weight;
 if (dist[u] != INT_MAX &&
dist[u] + weight < dist[v]) {
// Negative weight cycle detected
delete[] dist;
return -1;
}

current = current->next;
}
}

// Get the shortest path to destination

int result = dist[destination];

// Clean up
delete[] dist;

// Return result or -1 if no path exists

return (result == INT_MAX ? -1 : result);
}

void DirectedGraph::display() {
for (int i = 0; i < vertex; i++) {
cout << "Adjacency List of vertex " << i << ": ";
adjList[i].display();
}
}

int main() {
int n;
cout << "Enter Number of vertices in the Graph: ";
cin >> n;

if (n <= 0) {
cout << "Invalid number of vertices!" << endl;
return 0;
}

DirectedGraph A(n);
int ch = 0;
while (ch != 4) {
int u, v, weight;
cout << "\nMenu:\n"
<< "1. Add Edge\n"
<< "2. Display Graph\n"
<< "3. Run Bellman-Ford\n"
<< "4. Exit\n"
<< "Enter your choice: ";
cin >> ch;
switch (ch) {
case 1:
cout << "Enter edge (u, v) and its weight: ";
cin >> u >> v >> weight;
if ((u < n && u >= 0) && (v < n && v >= 0)) {
A.addEdge(u, v, weight);
} else {
cout << "Invalid vertices!" << endl;
}
 break;
case 2:
A.display();
break;
case 3:
cout << "Enter source and destination vertices: ";
cin >> u >> v;
if ((u < n && u >= 0) && (v < n && v >= 0)) {
int result = A.bellmanFord(u, v);
if (result == -1) {
cout << "No path exists or negative weight cycle detected
from vertex " << u << " to vertex " << v << endl;
} else {
cout << "Shortest Path from vertex " << u << " to vertex "
<< v << " : " << result << endl;
}
} else {
cout << "Invalid vertices!" << endl;
}
break;
case 4:
cout << "Exiting program." << endl;
break;
default:
cout << "Invalid choice!" << endl;
}
}

return 0;
}

Question 5. Write a program to implement a B-Tree.

#include <iostream>
#include <vector>
using namespace std;

// A B-Tree node
class BTreeNode {
public:
vector<int> keys; // A vector to store keys
vector<BTreeNode*> children; // A vector to store child pointers
bool isLeaf; // True if the node is a leaf
int t; // Minimum degree (defines the range for the number of keys)

BTreeNode(int degree, bool leaf);

void traverse();
BTreeNode* search(int key);
void insertNonFull(int key);
void splitChild(int i, BTreeNode* y);

friend class BTree;

};

// Constructor for B-Tree node

BTreeNode::BTreeNode(int degree, bool leaf) {
t = degree;
isLeaf = leaf;
}

// Traverse all nodes in a subtree rooted with this node

void BTreeNode::traverse() {
int i;
for (i = 0; i < keys.size(); i++) {
if (!isLeaf) {
children[i]->traverse();
}
cout << keys[i] << " ";
}
if (!isLeaf) {
children[i]->traverse();
}
}

// Search for a key in the subtree rooted with this node

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

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

return this;
}

if (isLeaf) {
return nullptr;
}

return children[i]->search(key);
}

// Insert a new key in this node (non-full)

void BTreeNode::insertNonFull(int key) {
int i = keys.size() - 1;

if (isLeaf) {
while (i >= 0 && keys[i] > key) {
i--;
}
keys.insert(keys.begin() + i + 1, key);
} else {
while (i >= 0 && keys[i] > key) {
i--;
}
if (children[i + 1]->keys.size() == 2 * t - 1) {
splitChild(i + 1, children[i + 1]);
if (keys[i + 1] < key) {
i++;
}
}
children[i + 1]->insertNonFull(key);
}
}
// Split the child of this node
void BTreeNode::splitChild(int i, BTreeNode* y) {
BTreeNode* z = new BTreeNode(y->t, y->isLeaf);
z->keys.assign(y->keys.begin() + t, y->keys.end());
y->keys.resize(t - 1);

if (!y->isLeaf) {
z->children.assign(y->children.begin() + t, y->children.end());
y->children.resize(t);
}

children.insert(children.begin() + i + 1, z);
keys.insert(keys.begin() + i, y->keys[t - 1]);
}

// A B-Tree
class BTree {
private:
BTreeNode* root;
int t;

public:
BTree(int degree) : root(nullptr), t(degree) {}

void traverse() {
if (root) {
root->traverse();
}
}

BTreeNode* search(int key) {

return root ? root->search(key) : nullptr;
}

void insert(int key) {

if (!root) {
root = new BTreeNode(t, true);
root->keys.push_back(key);
} else {
if (root->keys.size() == 2 * t - 1) {
BTreeNode* s = new BTreeNode(t, false);
s->children.push_back(root);
s->splitChild(0, root);
int i = (s->keys[0] < key) ? 1 : 0;
s->children[i]->insertNonFull(key);
root = s;
} else {
root->insertNonFull(key);
}
}
}
};

// Main function
int main() {
int degree, choice, value;
cout << "Enter the degree of the B-Tree: ";
cin >> degree;
 BTree tree(degree);

do {
cout << "\nB-Tree Operations:" << endl;
cout << "1. Insert" << endl;
cout << "2. Search" << endl;
cout << "3. Traverse" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
tree.insert(value);
break;
case 2:
cout << "Enter value to search: ";
cin >> value;
if (tree.search(value)) {
cout << value << " is found in the B-Tree." << endl;
} else {
cout << value << " is not found in the B-Tree." << endl;
}
break;
case 3:
cout << "B-Tree in sorted order: ";
tree.traverse();
cout << endl;
break;
case 4:
cout << "Exiting program. Thank you!" << endl;
break;
default:
cout << "Invalid choice. Please try again." << endl;
}
} while (choice != 4);

return 0;
}

//Question 6. Write a program to implement the Tree Data structure, which supports
the following operations:
// a. Insert
// b. Search

#include <iostream>
using namespace std;

// TreeNode class to represent a single node in the tree

class TreeNode {
public:
int data; // Data stored in the node
TreeNode* left; // Pointer to the left child
 TreeNode* right; // Pointer to the right child

// Constructor
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

// BinaryTree class to manage the tree structure and operations

class BinaryTree {
private:
TreeNode* root; // Pointer to the root of the tree

// Helper function to insert a node recursively

TreeNode* insertNode(TreeNode* node, int value) {
if (node == nullptr) {
// Create a new node if the current position is empty
return new TreeNode(value);
}
if (value < node->data) {
// Insert in the left subtree if the value is smaller
node->left = insertNode(node->left, value);
} else if (value > node->data) {
// Insert in the right subtree if the value is larger
node->right = insertNode(node->right, value);
}
return node; // Return the unchanged node pointer
}

// Helper function to search for a value recursively

bool searchNode(TreeNode* node, int value) {
if (node == nullptr) {
// If the node is null, the value is not found
return false;
}
if (node->data == value) {
// Value is found
return true;
}
if (value < node->data) {
// Search in the left subtree
return searchNode(node->left, value);
} else {
// Search in the right subtree
return searchNode(node->right, value);
}
}

// Helper function for in-order traversal

void inOrderTraversal(TreeNode* node) {
if (node != nullptr) {
inOrderTraversal(node->left);
cout << node->data << " ";
inOrderTraversal(node->right);
}
}

public:
// Constructor
BinaryTree() : root(nullptr) {}
 // Insert a value into the tree
void insert(int value) {
root = insertNode(root, value);
cout << "Inserted " << value << " into the tree." << endl;
}

// Search for a value in the tree

void search(int value) {
if (searchNode(root, value)) {
cout << value << " is found in the tree." << endl;
} else {
cout << value << " is not found in the tree." << endl;
}
}

// Display the tree in in-order traversal

void display() {
cout << "Tree in in-order traversal: ";
inOrderTraversal(root);
cout << endl;
}
};

// Main function
int main() {
BinaryTree tree;
int choice, value;

do {
cout << "\nBinary Tree Operations:" << endl;
cout << "1. Insert" << endl;
cout << "2. Search" << endl;
cout << "3. Display" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
tree.insert(value);
break;
case 2:
cout << "Enter value to search: ";
cin >> value;
tree.search(value);
break;
case 3:
tree.display();
break;
case 4:
cout << "Exiting program. Thank you!" << endl;
break;
default:
cout << "Invalid choice. Please try again." << endl;
}
} while (choice != 4);
 return 0;
}

Question 7. Write a program to search a pattern in a given text using the KMP
algorithm.

#include <iostream>
#include <vector>
#include <string>
#include <limits>

using namespace std;

class KMPSearch {
public:
// Compute the longest proper prefix which is also a suffix array
static vector<int> computeLPSArray(const string& pattern) {
int m = pattern.length();
vector<int> lps(m, 0);

int len = 0; // Length of the previous longest prefix suffix

int i = 1;

while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
}
else {
// If characters don't match
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
return lps;
}

// KMP search algorithm

static vector<int> search(const string& text, const string& pattern) {
vector<int> result;

// Compute the longest prefix suffix (LPS) array

vector<int> lps = computeLPSArray(pattern);

int n = text.length();
int m = pattern.length();

int i = 0; // Index for text

 int j = 0; // Index for pattern

while (i < n) {
// If characters match, increment both indices
if (pattern[j] == text[i]) {
j++;
i++;
}

// If pattern is completely matched, store the starting index

if (j == m) {
result.push_back(i - j);
j = lps[j - 1];
}
// Mismatch after some matches
else if (i < n && pattern[j] != text[i]) {
// Do not match lps[0..lps[j-1]] characters
if (j != 0) {
j = lps[j - 1];
}
else {
i++;
}
}
}

return result;
}
};

int main() {
string text, pattern;
char choice;

do {
// Clear input buffers
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');

// Get text from user

cout << "Enter the text to search in: ";
getline(cin, text);

// Get pattern from user

cout << "Enter the pattern to search for: ";
getline(cin, pattern);

// Perform KMP search

vector<int> occurrences = KMPSearch::search(text, pattern);

// Print results
cout << "\nSearch Results:" <<endl;
cout << "Text: " << text <<endl;
cout << "Pattern: " << pattern <<endl;

if (occurrences.empty()) {
cout << "Pattern not found in the text." << endl;
}
else {
 cout << "Pattern found at following starting indices:" <<endl;
for (int index : occurrences) {
cout << index << " ";
}
cout << endl;
}

// Ask if user wants to continue

cout << "\nDo you want to search again? (y/n): ";
cin >> choice;

} while (choice == 'y' || choice == 'Y');

cout << "Thank you for using KMP Pattern Search!" << endl;
return 0;
}

Question 8. Write a program to implement a Suffix tree.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <memory>
#include <limits>

using namespace std;

class SuffixTreeNode {
public:
unordered_map<char, shared_ptr<SuffixTreeNode>> children;
shared_ptr<SuffixTreeNode> suffixLink;
int start;
int* end;
int suffixIndex;

SuffixTreeNode(int start = -1, int* end = nullptr) :

start(start),
end(end),
suffixIndex(-1) {}
};

class SuffixTree {
private:
string text;
shared_ptr<SuffixTreeNode> root;
shared_ptr<SuffixTreeNode> lastNewNode;
shared_ptr<SuffixTreeNode> activeNode;
int activeEdge;
int activeLength;
int remainingSuffixCount;
int leafEnd;
int* rootEnd;
int size;

bool walkDown(shared_ptr<SuffixTreeNode>& currentNode) {

int edgeLength = getEdgeLength(currentNode);
 if (activeLength >= edgeLength) {
activeEdge += edgeLength;
activeLength -= edgeLength;
activeNode = currentNode;
return true;
}
return false;
}

int getEdgeLength(shared_ptr<SuffixTreeNode>& node) {

if (node == root)
return 0;
return *(node->end) - node->start + 1;
}

void extendSuffixTree(int phase) {

leafEnd = phase;
remainingSuffixCount++;
lastNewNode = nullptr;

while (remainingSuffixCount > 0) {

if (activeLength == 0)
activeEdge = phase;

auto currentChild = activeNode->children.find(text[activeEdge]);

if (currentChild == activeNode->children.end()) {
activeNode->children[text[activeEdge]] =
make_shared<SuffixTreeNode>(phase, &leafEnd);

if (lastNewNode != nullptr) {
lastNewNode->suffixLink = activeNode;
lastNewNode = nullptr;
}
}
else {
shared_ptr<SuffixTreeNode> next = currentChild->second;

if (walkDown(next))
continue;

if (text[next->start + activeLength] == text[phase]) {

if (lastNewNode != nullptr) {
lastNewNode->suffixLink = activeNode;
lastNewNode = nullptr;
}

activeLength++;
break;
}

int splitEnd = next->start + activeLength - 1;

auto splitNode = make_shared<SuffixTreeNode>(next->start,
&splitEnd);

activeNode->children[text[activeEdge]] = splitNode;

splitNode->children[text[phase]] =
 make_shared<SuffixTreeNode>(phase, &leafEnd);

next->start += activeLength;
splitNode->children[text[next->start]] = next;

if (lastNewNode != nullptr) {
lastNewNode->suffixLink = splitNode;
}
lastNewNode = splitNode;
}

remainingSuffixCount--;

if (activeNode == root && activeLength > 0) {

activeEdge = phase - remainingSuffixCount + 1;
activeLength--;
}
else if (activeNode != root) {
activeNode = activeNode->suffixLink ? activeNode->suffixLink :
root;
}
}
}

void printTree(shared_ptr<SuffixTreeNode> node, int depth = 0) {

for (auto& child : node->children) {
for (int i = 0; i < depth; i++)
cout << " ";

int start = child.second->start;

int end = *(child.second->end);
cout << text.substr(start, end - start + 1) << endl;

printTree(child.second, depth + 1);

}
}

public:
SuffixTree() {
root = make_shared<SuffixTreeNode>();
rootEnd = new int(-1);
root->end = rootEnd;
activeNode = root;
size = 0;
}

void buildSuffixTree(const string& input) {

root = make_shared<SuffixTreeNode>();
root->end = rootEnd;
activeNode = root;
activeEdge = -1;
activeLength = 0;
remainingSuffixCount = 0;
leafEnd = -1;

text = input + "$";

size = text.length();

for (int i = 0; i < size; i++) {

 extendSuffixTree(i);
}
}

void searchPattern(const string& pattern) {

if (text.empty()) {
cout << "Suffix tree not built. Build tree first." << endl;
return;
}

shared_ptr<SuffixTreeNode> currentNode = root;

int patternIndex = 0;

while (patternIndex < pattern.length()) {

auto child = currentNode->children.find(pattern[patternIndex]);

if (child == currentNode->children.end()) {
cout << "Pattern not found in the text." << endl;
return;
}

shared_ptr<SuffixTreeNode> nextNode = child->second;

int edgeStart = nextNode->start;
int edgeEnd = *(nextNode->end);
int j = edgeStart;

while (j <= edgeEnd && patternIndex < pattern.length()

&& text[j] == pattern[patternIndex]) {
j++;
patternIndex++;
}

if (patternIndex == pattern.length()) {
cout << "Pattern found in the text." << endl;
return;
}

if (j <= edgeEnd || patternIndex >= pattern.length()) {

cout << "Pattern not found in the text." << endl;
return;
}

currentNode = nextNode;
}
}

void displayTree() {
if (text.empty()) {
cout << "Suffix tree not built. Build tree first." << endl;
return;
}
cout << "Suffix Tree Structure:" << endl;
printTree(root);
}

~SuffixTree() {
delete rootEnd;
}
};
int main() {
SuffixTree suffixTree;
int choice;
string input, pattern;

while (true) {
cout << "\n--- Suffix Tree Operations ---" << endl;
cout << "1. Build Suffix Tree" << endl;
cout << "2. Search Pattern" << endl;
cout << "3. Display Suffix Tree" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;

cin.ignore(numeric_limits<streamsize>::max(), '\n');

switch (choice) {
case 1:
cout << "Enter the text to build suffix tree: ";
getline(cin, input);
suffixTree.buildSuffixTree(input);
cout << "Suffix tree built successfully!" << endl;
break;

case 2:
cout << "Enter pattern to search: ";
getline(cin, pattern);
suffixTree.searchPattern(pattern);
break;

case 3:
suffixTree.displayTree();
break;

case 4:
cout << "Exiting program..." << endl;
return 0;

default:
cout << "Invalid choice. Please try again." << endl;
}
}

return 0;
}

//Question 8. Suffix Tree using brute force

#include <iostream>
#include <string>
#include<limits>
#include <unordered_map>
using namespace std;
// A node in the suffix trie
class SuffixTrieNode {
public:
unordered_map<char, SuffixTrieNode*> children;

// Insert a suffix starting from this node

void insertSuffix(const string& suffix) {
SuffixTrieNode* current = this;
for (char ch : suffix) {
if (current->children.find(ch) == current->children.end()) {
current->children[ch] = new SuffixTrieNode();
}
current = current->children[ch];
}
}

~SuffixTrieNode() {
for (auto& child : children) {
delete child.second;
}
}
};

// Suffix trie class

class SuffixTrie {
private:
SuffixTrieNode* root;
string text;

public:
SuffixTrie() : root(new SuffixTrieNode()) {}

// Build the suffix trie by inserting all suffixes of the text

void buildSuffixTrie(const string& input) {
text = input + "$"; // Add a unique termination character
for (size_t i = 0; i < text.length(); ++i) {
root->insertSuffix(text.substr(i));
}
}

// Search for a pattern in the suffix trie

bool searchPattern(const string& pattern) {
SuffixTrieNode* current = root;
for (char ch : pattern) {
if (current->children.find(ch) == current->children.end()) {
return false;
}
current = current->children[ch];
}
return true;
}

// Print all suffixes in the trie (DFS traversal)

void printSuffixes(SuffixTrieNode* node, const string& prefix) {
if (node->children.empty()) {
cout << prefix << endl;
return;
}
 for (const auto& child : node->children) {
printSuffixes(child.second, prefix + child.first);
}
}

void displayTrie() {
cout << "Suffix Trie Structure:" << endl;
printSuffixes(root, "");
}

~SuffixTrie() {
delete root;
}
};

// Main function
int main() {
SuffixTrie suffixTrie;
string input, pattern;
int choice;

while (true) {
cout << "\n--- Suffix Trie Operations ---" << endl;
cout << "1. Build Suffix Trie" << endl;
cout << "2. Search Pattern" << endl;
cout << "3. Display Suffix Trie" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;

cin.ignore(numeric_limits<streamsize>::max(), '\n');

switch (choice) {
case 1:
cout << "Enter the text to build suffix trie: ";
getline(cin, input);
suffixTrie.buildSuffixTrie(input);
cout << "Suffix trie built successfully!" << endl;
break;

case 2:
cout << "Enter pattern to search: ";
getline(cin, pattern);
if (suffixTrie.searchPattern(pattern)) {
cout << "Pattern found in the text." << endl;
} else {
cout << "Pattern not found in the text." << endl;
}
break;

case 3:
suffixTrie.displayTrie();
break;

case 4:
cout << "Exiting program..." << endl;
return 0;
 default:
cout << "Invalid choice. Please try again." << endl;
}
}

return 0;
}