Cracking the Piggy Bank Puzzle: A Java Adventure in Dynamic Programming

Hey there, intrepid coders! Today, we're diving into a piggy bank heist… of the intellectual kind, of course! We'll be using a powerful technique called Dynamic Programming (DP) to crack the code of a mischievous piggy bank and unlock its hidden treasures. Buckle up, because this adventure requires both logic and a dash of mathematical magic.

Imagine a piggy bank with compartments numbered 1 to N. Each compartment holds a certain amount of coins. Your mission is to maximise the total coins you can collect by following these two rules:

1. You can only start at compartment 1 and move rightward, collecting all the coins in a compartment before proceeding.
2. You can either skip a compartment (earning you 0 coins) or rob a compartment, but robbing two consecutive compartments is forbidden.

This might seem tricky, but DP comes to the rescue! It breaks down the problem into smaller, overlapping subproblems and cleverly stores the solutions, saving you from redundant calculations. Think of it like mapping a treasure hunt – each solution to a subproblem guides you towards the bigger prize.

class PiggyBankBreaker {

    private final int[] coins; // Array storing coins in each compartment (1-indexed)
    private final int[] maxCoins; // DP array to store max achievable coins at each position (0-indexed)

    public PiggyBankBreaker(int[] coins) {
        this.coins = coins; // Copy original coin values
        this.maxCoins = new int[coins.length + 1]; // Allocate DP array with space for starting point (index 0)
    }

    public int crackPiggyBank() {
        // Base case: No coins at starting point
        maxCoins[0] = 0;

        // Loop through each compartment from index 1 (inclusive)
        for (int i = 1; i <= coins.length; i++) {
            // Option 1: Rob current compartment + max from 2 positions back (non-consecutive)
            int robCurrent;

            // Check if robbing current is even possible (avoid accessing coins[-1])
            if (i >= 3) {
                robCurrent = coins[i - 1] + maxCoins[i - 3];
            } else {
                // Default to skipping for initial positions where robbing isn't valid
                robCurrent = 0;
            }

            // Option 2: Skip current compartment and take max from previous position (consecutive)
            int skipCurrent = maxCoins[i - 1];

            // Choose the option that yields more coins
            maxCoins[i] = Math.max(robCurrent, skipCurrent);
        }

        // Return the maximum achievable coins from the last compartment
        return maxCoins[coins.length];
    }

    public static void main(String[] args) {
        // Example piggy bank with coins
        int[] coins = {2, 3, 1, 4, 5, 7, 10};

        PiggyBankBreaker breaker = new PiggyBankBreaker(coins);
        int maxLoot = breaker.crackPiggyBank();
        System.out.println("Maximum amount you can collect: " + maxLoot);
    }
}

This Java code solves the piggy bank problem, where you maximise the coins collected while adhering to two rules:

1. Start at compartment 1 and move rightward, collecting all coins in each compartment.
2. You can either skip or rob a compartment, but not two consecutive compartments.

The code utilises Dynamic Programming (DP) to efficiently solve this problem by breaking it down into smaller, overlapping subproblems. Here's a breakdown of the key aspects:

• The method calculates the maximum coins achievable from any starting point.
• Base case: maxCoins[0] = 0 since no coins are earned before starting.
• Loop: Iterates through each compartment (index 1 to length).
• Rob current option:
  • Calculates robCurrent by adding the current coin value (coins[i - 1]) to the maximum coins achievable two positions back (maxCoins[i - 3]).
  • Fix: A conditional statement (i >= 3) ensures this calculation only happens for valid positions (avoiding coins[-1] access).
  • Otherwise, robCurrent is set to 0, mimicking skipping the compartment for initial positions.
• Skip current option: Simply takes the maximum coins from the previous position (maxCoins[i - 1]).
• Comparison: Chooses the maximum value between robCurrent and skipCurrent and stores it in maxCoins[i]. This ensures the optimal decision is recorded for future subproblems.
• Final result: The last element maxCoins[coins.length] represents the maximum achievable coins from the starting point (compartment 1).

Longest common subsequence in Java

Longest Common Subsequence (LCS)

• It's the longest sequence of characters that is present in the same relative order within two or more strings.
• It doesn't have to be a contiguous substring; the characters can appear in different positions within the original strings.

Understanding the Problem

• Imagine two strings, written vertically on separate columns.
• The goal is to find the longest sequence of characters that appears in the same order within both strings, even if they're not consecutive.

Character Grid

• Create a grid where each row represents a character from the first string, and each column represents a character from the second string.
• Fill each cell with a color indicating whether the corresponding characters match (e.g., green) or not (e.g., white).

Tracing Paths

• Start at the top-left corner of the grid.
• Move diagonally down-right only when characters match (green cells).
• If characters don't match, move either down or right to continue searching for matches.
• The path you take represents the LCS.

Visualize the LCS

• Highlight the cells along the longest path with a bolder color or border.
• The characters in those cells, read in order, form the LCS.

Example:

Consider strings "AGGTAB" and "GXTXAYB":

LCS: "GTAB" (highlighted cells)

Algorithm

1. Dynamic Programming Table:

   • Create a 2D table dp with dimensions (m+1) x (n+1), where m and n are the lengths of the two strings.
   • Fill the first row and column with 0s, indicating no LCS for empty strings.

2. Filling the Table:

   • Iterate through the table, starting from dp[1][1].
   • For each cell dp[i][j]:
     • If the characters at indices i-1 and j-1 in the strings match:
       • Set dp[i][j] = dp[i-1][j-1] + 1 (add 1 to the LCS length of the previous substrings).
     • Else:
       • Set dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the maximum LCS length from the previous options).

3. Reconstructing the LCS:

   • Start from the bottom-right corner of the table (dp[m][n]).
   • Backtrack:
     • If the characters at indices i-1 and j-1 match, add the character to the LCS and move diagonally up (i--, j--).
     • Else, move to the cell with the maximum value (either i-- or j--).
   • Reverse the constructed LCS string to get the correct order.

 

public class LCS {

    public static String lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];

        // Build the table in a bottom-up manner
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Reconstruct the LCS
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // Reverse the LCS string
        return lcs.reverse().toString();
    }

    // Example usage for testing
    public static void main(String[] args) {
        System.out.println(lcs("ABCDEFG", "BCDGK"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("ABCDE", "A"));
        System.out.println(lcs("A", "BCDEF"));
    }
}

Explanation for code

1. lcs() Method:

• Takes two strings as input.
• Uses dynamic programming to find the longest common subsequence (LCS).
• Returns the LCS string.

Steps

• Create a DP Table: Stores the lengths of LCSs for substrings of different lengths.
• Fill the DP Table:
  • Iterates through characters of both strings.
  • For each cell, calculates the length of the LCS based on previous calculations:
    • If characters match, add 1 to the LCS length of the previous substrings.
    • If not, take the maximum LCS length from the previous options.
• Reconstruct the LCS: Backtracks through the DP table to find the characters in the LCS.
• Reverse the LCS: Since it's built backward, reverse it before returning.

Take away points

• Bottom-up approach: Builds the solution from smaller subproblems to the final LCS.
• Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
• Time complexity: O(mn), where m and n are string lengths.
• Space complexity: O(mn), due to the DP table.

Knapsack Problem implementation in Java

Imagine a hiker's backpack (the knapsack) with limited space (capacity).

They have a collection of items, each with a value (usefulness) and a weight (space it occupies).

The goal is to fill the backpack with the most valuable combination of items, without exceeding its weight capacity.

Visualizing the Items

Item 1:  (value 60, weight 10)
Item 2:  (value 100, weight 20)
Item 3:  (value 120, weight 30)

The Knapsack

Decision-Making

• Can't fit all items directly (total weight 60).
• Optimal choice would be to put these items in the bag
  
• Item: {value: 120, weight: 30}
• Item: {value: 100, weight: 20}

Optimal Solution

KNAPSACK  (capacity 50)
     (value 120, weight 30)

Key Points

• Knapsack represents a resource constraint (limited capacity).
• Items represent choices with associated values and constraints (weight).
• Goal is to maximize value within the constraint.
• Often involves trade-offs and strategic decision-making.

In formal language, given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, find the subset of items that maximizes the total value while fitting within the weight capacity.

Dynamic Programming Approach

1. Create a table dp:

   • Dimensions: (n + 1) x (W + 1), where n is the number of items and W is the knapsack capacity.
   • dp[i][w] stores the maximum value achievable using items up to the i-th item and with a maximum weight of w.

2. Fill the table:

   • Base cases:
     • dp[0][w] = 0 for all w (no items, value is 0).
     • dp[i][0] = 0 for all i (zero weight capacity, value is 0).
   • Recursive formula:
     • dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w (Choose between including or excluding the i-th item)
     • dp[i][w] = dp[i-1][w] otherwise (Item cannot be included due to weight constraint)

3. Solution:

• The maximum value is dp[n][W] (using all items with the knapsack capacity).
• Backtrack to find the selected items.

import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    public static List knapsack(List items, int capacity) {
        int[][] dp = new int[items.size() + 1][capacity + 1];

        // Build table dp[][] in a bottom-up manner
        for (int i = 0; i <= items.size(); i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (items.get(i - 1).weight <= w) {
                    dp[i][w] = Math.max(items.get(i - 1).value + dp[i - 1][w - items.get(i - 1).weight], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // Reconstruct the solution
        List selectedItems = new ArrayList<>();
        int i = items.size(), w = capacity;
        while (i > 0 && w > 0) {
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(items.get(i - 1));
                w -= items.get(i - 1).weight;
            }
            i--;
        }

        return selectedItems;
    }

    public static void main(String[] args) {
        List items = new ArrayList<>();
        items.add(new Item(60, 10));
        items.add(new Item(100, 20));
        items.add(new Item(120, 30));
        int capacity = 50;

        List selected = knapsack(items, capacity);
        System.out.println("Selected items: " + selected);
    }

    public static class Item {
        int value;
        int weight;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Item: {value: " + value + ", weight: " + weight + "}";
        }
    }
}

Explanation of code

1. Item Class:

• Represents an item with its value and weight.

2. knapsack() Method:

• Takes a list of items and a knapsack capacity as input.
• Uses dynamic programming to solve the 0-1 Knapsack Problem.
• Returns a list of selected items that maximize the total value without exceeding the capacity.

Steps

• Create a 2D DP array: Stores intermediate results for subproblems.
• Fill the DP array:
  • Iterate through items and capacities.
  • For each cell, calculate the maximum value achievable considering the current item and remaining capacity.
• Reconstruct the solution: Backtrack through the DP array to find the selected items.

Take away points

• Bottom-up approach: Builds the solution from smaller subproblems to the final solution.
• Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
• Time complexity: O(nW), where n is the number of items and W is the capacity.
• Space complexity: O(nW), due to the DP array.

Dijkstra algorithm implementation in Java

Purpose

• Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
• Commonly used in GPS navigation, network routing, and logistics planning.

Key Concepts

• Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
• Source Vertex: The starting point for finding shortest paths.
• Shortest Path: The path with the minimum total weight between two vertices.

Algorithm Steps

1. Initialization:

   • Create a set S to store visited vertices (initially empty).
   • Initialize an array distances with infinite values for all vertices except the source, which is set to 0.
   • Create a priority queue Q to store vertices, prioritized by their tentative distances.
   • Add the source vertex to Q.

2. Exploration Loop:

   • While Q is not empty:
     • Extract the vertex u with the minimum distance from Q.
     • Add u to the set S (mark as visited).
     • For each neighbor vertex v of u:
       • If v is not visited and the distance to v through u is shorter than its current distance:
         • Update the distance to v in the distances array.
         • Add v to the priority queue Q (or update its priority if already present).

3. Result:

   • The distances array now contains the shortest distances from the source vertex to all other vertices.
   • To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

public class Dijkstra {

    public static List dijkstra(Graph graph, int source) {
        int[] distances = new int[graph.numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
        pq.offer(source);

        boolean[] visited = new boolean[graph.numVertices];
        while (!pq.isEmpty()) {
            int u = pq.poll();
            visited[u] = true;
            for (Edge edge : graph.adjacencyList.get(u)) {
                int v = edge.to;
                int weight = edge.weight;
                if (!visited[v] && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    pq.offer(v);
                }
            }
        }

        return Arrays.stream(distances).boxed().collect(Collectors.toList());
    }

    public static Graph createRandomGraph(int numVertices) {
        Graph graph = new Graph(numVertices);
        Random random = new Random();
        // Add edges with random weights
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                // Decide whether to create an edge with 50% probability
                if (random.nextBoolean()) {
                    int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
                    graph.addEdge(i, j, weight);
                    graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
                }
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = createRandomGraph(9);
        graph.visualize();
        int source = 0;
        List distances = dijkstra(graph, source);
        System.out.println("Shortest distances from " + source + ": " + distances);
    }

    public static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Graph {
        int numVertices;
        List> adjacencyList;

        Graph(int numVertices) {
            this.numVertices = numVertices;
            adjacencyList = new ArrayList<>();
            for (int i = 0; i < numVertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to, int weight) {
            adjacencyList.get(from).add(new Edge(to, weight));
        }

        void visualize() {
            System.out.println("Graph Visualization:\n");
            for (int vertex = 0; vertex < numVertices; vertex++) {
                System.out.print(vertex + " -> ");
                for (Edge edge : adjacencyList.get(vertex)) {
                    System.out.print(edge.to + "(" + edge.weight + ") ");
                }
                System.out.println();
            }
        }
    }
}

Explanation of code

• Graph Representation

  • The Graph class models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights.
  • The Edge class encapsulates the destination vertex and weight of an edge.

• Dijkstra's Algorithm Implementation

  • The dijkstra(Graph, source) method implements the algorithm's logic:
    • It maintains a priority queue to explore vertices in order of their tentative distances.
    • It iteratively relaxes edges to update distances and explore reachable vertices.
    • It ultimately returns a list of the shortest distances from the source vertex to all other vertices.

• Random Graph Generation

  • The createRandomGraph(numVertices) method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.

Ternary Search Tree Implementation in C++

A Ternary Search Tree is a trie which leverages concepts of Binary Search Tree as well. A Ternary Search Tree is as memory efficient as Binary Search Trees and time efficient as a Trie.

It is an efficient data structure to store and search large number of strings.

A node in a Ternary Search Tree comprises of these fields :

• Left pointer - Points to Ternary Search Tree containing all strings alphabetically lesser than current node's data
• Right pointer - Points to Ternary Search Tree containing all strings alphabetically greater than current node's data
• Equal pointer - Points to Ternary Search Tree containing all strings alphabetically equal to current node's data
• End of string flag - Flag indicating the end of string
• Data - Actual data in the form of single character

Ternary Search Tree Node

For example, consider adding these strings in the same order into a Ternary Search Tree :

1. "Lead"
2. "Leader"
3. "Leads"
4. "Late"
5. "State"

Let's build a visualization of ternary search tree out of above data :

1. "Lead"
   
2. "Leader"
   
   
3. "Leads"
   
   
4. "Late"
   
   
5. "State"
   

//TST.h
#ifndef TST_H
#define TST_H
//#define DEBUG_PROGRAM_MEMORY

//Node of a Ternary Search Tree
typedef struct TSTNode{
 char data; //Actual data stored in form of character
 bool bEOS; //flag marking end of string
 struct TSTNode* left;   //All character data less than this node
 struct TSTNode* eq;  //All character data equal to this node
 struct TSTNode* right; //All character data greater than this node
}TSTNode;

//Inserts a string in the TST
TSTNode* Insert(TSTNode* root, char* str); 

//Prints all strings in the TST
void PrintAllStringsInTST(TSTNode* root);

//Gets the length of maximum length string in TST
int MaxLenStringLen(TSTNode *root);

//Deleted the complete TST
void DeleteTST(TSTNode *root);

//Search a pattern in TST
bool SearchTST(TSTNode *root, char* pattern);

//Prints 
#ifdef DEBUG_PROGRAM_MEMORY
#include <map>

static std::map<TSTNode*, char> mem_addrs;
void CheckTSTMem();
#endif

#endif

//TST.cpp
#include <iostream>
#define DEBUG_PROGRAM_MEMORY

#include "TST.h"
#include <cstdlib>
#include <utility>

#define MAX_LEN 1024

#define MAX( a, b, c ) ((a)>(b) ? ((a)>(c) ? (a):(c)) : ( (b)>(c) ? (b):(c) ))


TSTNode* Insert(TSTNode* root, char* str)
{
 if(root == NULL)
 {
  root = (TSTNode*)malloc(sizeof(TSTNode));
  if(root == NULL)
  {
   std::cout<<"Memory allocation failed"<<std::endl;
   return NULL;
  }

  //Insert first character of string in the root node
  root->data = *str;
#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.insert(std::make_pair(root, root->data));
#endif
  root->bEOS = false;
  root->left = root->eq = root->right = NULL;
 }
 
 if(*str  < root->data)
  root->left = Insert(root->left, str);
 else if (*str == root->data)
 {
  if(*(str + 1))
   root->eq = Insert(root->eq, str + 1);
  else
   root->bEOS = true;
 }
 else
  root->right = Insert(root->right, str);
 
 return root; 
}

//Helper to print the strings in TST
static void PrintHelper(TSTNode* root, char* buffer, int depth)
{
 if (root)
 {
  // Traverse the left subtree
  PrintHelper(root->left, buffer, depth);

  buffer[depth] = root->data;
  //Once end of string flag is encountered, print the string
  if (root->bEOS)
  {
   buffer[depth + 1] = '\0';
   std::cout<< buffer << std::endl;
  }

  // Traverse the middle subtree
  PrintHelper(root->eq, buffer, depth + 1);

  // Traverse the right subtree
  PrintHelper(root->right, buffer, depth);
 }
}

// Function to print TST's strings
void PrintAllStringsInTST(TSTNode* root)
{
 char buffer[MAX_LEN];
 PrintHelper(root, buffer, 0);
}

bool SearchTST(TSTNode *root, char* pattern)
{
 while (root != NULL)
 {
  if (*pattern < root->data)
   root = root->left;
  else if (*pattern == root->data)
  {
   //If end of string flag is found and the pattern length is also exhausted, 
   //we can safely say that the pattern is present in the TST
   if (root->bEOS && *(pattern + 1) == '\0')
    return true;
   pattern++;
   root = root->eq;
  }
  else
   root = root->right;
 }

 return false;
}

//Function to determine largest 
int MaxLenStringLen(TSTNode *root)
{
 if (root == NULL)
  return 0;

 int leftLen = MaxLenStringLen(root->left);
 int middleLen = MaxLenStringLen(root->eq) + 1;
 int rightLen = MaxLenStringLen(root->right);

 return MAX( leftLen, middleLen, rightLen);
}

void DeleteTST(TSTNode *root)
{
 TSTNode *tmp = root;
 if (tmp)
 {
  DeleteTST(tmp->left);
  DeleteTST(tmp->eq);
  DeleteTST(tmp->right);

#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.erase(tmp);
#endif
  delete tmp;
 }
}

#ifdef DEBUG_PROGRAM_MEMORY
void CheckTSTMem()
{
 std::map<TSTNode*, char>::iterator itr = mem_addrs.begin();

 if (mem_addrs.size() == 0)
 {
  std::cout << "No memory leaks";
  return;
 }

 while (itr != mem_addrs.end()) 
 {
  std::cout << "Memory address " << itr->first<< " for \"" << itr->second << "\" has not been deallocated" << std::endl;
  ++itr;
 }
}
#endif

//Main.cpp
#include <iostream>
#include "TST.h"

int main(int argc, char** argv) {
 
 TSTNode *root = NULL;
 root = Insert(root, "boats");
 root = Insert(root, "boat");
 root = Insert(root, "bat");
 root = Insert(root, "bats");
 root = Insert(root, "stages");

 PrintAllStringsInTST(root);
 std::cout << "Maximum length string in this TST is of size "<< MaxLenStringLen(root) << std::endl;

 char *str = "hello";
 char *str1 = "bat";

 if (SearchTST(root, str) == false)
  std::cout << "\""<<str<<"\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str << "\" is present in TST" << std::endl;

 if (SearchTST(root, str1) == false)
  std::cout << "\"" << str << "\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str1 << "\" is present in TST" << std::endl;

 DeleteTST(root);

#ifdef DEBUG_PROGRAM_MEMORY
 CheckTSTMem();
#endif
 
 return 0;
}

String matching using KMP algorithm : C++ Implementation

KMP Algorithm is one the well-known string matching algorithms. It finds a pattern in a string. The pattern can exist multiple times in the string. This implementation in C++ gives indexes of all such matches in the string to be searched.

e.g. 

String to be searched : "ABCDBCAAB ABCDABCDABDE ABCDABD"
Pattern : "ABCD"

The result will be 4 index locations 0, 10, 14 and 23

 However, there is a limitation of KMP algorithm where the pattern overlaps.

 Consider this scenario :

 String to be searched: "ABCABCABCA"
 Pattern: "ABCA"
 The result from KMP algorithm will be 0 and 6 locations. It cannot identify the overlapping matches  like this:
 ABCABCABCA
 ABCABCABCA
 ABCABCABCA

#include <iostream>
#include <cstdlib>

using namespace std;
#define MAX_MATCHES 100

//Array to store matched indexes
int FOUND[MAX_MATCHES];
//variable to store last index in FOUND array
static int l = 0;

//Partial match table
void kmp_table(string W, int *T )
{
 int pos = 2;
 int cnd = 0;
 int length = W.length();
 
 T[0] = -1;
 T[1] = 0;
 
 while( pos < length)
 {
  if(W[pos-1] == W[cnd])
  {
   T[pos] = cnd + 1;
   cnd++;
   pos++;
  }
  else if( cnd > 0)
   cnd = T[cnd];
  else
  {
   T[pos] = 0;
   pos++;
  }
 }
}

//Search function
void kmp_search(string S, string W)
{
 
 int m = 0; 
 int i = 0;
 int sizeS = S.length();
 int sizeW = W.length();
 
 int *T = new int[sizeof(int) * sizeW];
 
 kmp_table(W, T);
 
 while( (m + i) < sizeS)
 {
  if (W[i] == S[m + i]) 
  {
            if (i == (sizeW - 1))
            {
             //Add the start index of match in the FOUND table
             FOUND[l++] = m;
   }
    
            i++;
        }
        else
        {
            if (T[i] > -1)
            {
                m = m + i - T[i];
    i = T[i];
            }
            else
            {
                m = m + 1;
    i = 0;
            }
        }
 }
 
 delete(T);
}

int main()
{
 string S = "ABCDBCAAB ABCDABCDABDE ABCDABD";
 string W = "ABCD";
 
 kmp_search(S,W);
  
 for (int i = 0 ; i < l; i++)
  cout<<"Pattern found at "<< FOUND[i] <<endl; 
}

Component Object Model(COM) - Implementation in C++ -- Usage in C++, C#

As per Microsoft "Component Object Model or COM is a platform-independent, distributed, object-oriented system for creating binary software components that can interact".
COM defines a standard (Object Model) and the implementation part is left to the developer. These objects can communicate within a process or across the processes,  on the same or different machine with different programming languages.

Language requirement for COM :

1. Ability to create structures of pointers

2. Ability to call functions using pointers

Object-oriented languages such as C++ and Smalltalk provide programming mechanisms that simplify the implementation of COM objects, but languages such as C, Java, and VBScript can be used create and use COM objects.

Object's data is accessed using interfaces. The functions of this interface are called methods. The pointers to these interfaces enables to call the methods.

More information on COM is available at the MSDN .

In a nutshell , COM provides interfaces which can be implemented in different languages and can be used over distributed platforms.

To provide portability across platforms and programming languages, COM uses interface definition in platform-independent language, IDL(Interface Definition Language).

Steps involved to create COM interface:

1. Define the interface/s in .idl file.
2. Compile the .idl file using IDL compiler(platform and language specific) to generate language and platform specific code.
3. Implement these interface/s in the specific language.
4. Use it.

In our example, we are using MIDL compiler to generate the C++ specific code and DLL.
We will use ATL to make the implementation easier. ATL is the Active Template Library, a set of template-based C++ classes with which you can easily create small, fast Component Object Model (COM) objects. It has special support for key COM features including: stock implementations of IUnknown, IClassFactory, IClassFactory2, and IDispatch; dual interfaces; standard COM enumerator interfaces; connection points; tear-off interfaces; and ActiveX controls.

We are using Visual Studio 2005 for our example. Visual Studio provides ATL project wizard which will help a lot and make the process easy.

Steps to generate COM DLL:

1. Create a new project in Visual Studio File->New->Project->Visual C++ -> ATL => ATL Project.
   

   

   
   

   
   
2. Give the project name as Calculator as we will be implementing a calculator interface using COM.
   
   
   
3. Choose DLL(Dynamic-link library) in the Application Settings -> Finish.
   
   
   
   
   
4. This structure will be visible once the project is created.
   
   
   
   
   
5. Now add a class following the image as below. Right click on the project Add->Class.
   
   
   
   
   
6. We will now add a COM Object using ATL Simple Object.
   
   
   
   
   
7. Give the name of class as CalculatorImpl (This defines the implentation of the interface). You can see under the panel C++ these four areas are updated -> Short Name, .h file, Class, .cpp file to be as CalculatorImpl, CalculatorImpl.h , CCalculatorImpl and CalculatorImpl.cpp respectively . Also in the panel COM below, these four areas are also updated - CoClass, Type, Interface and ProgID. Change these according to the image below.
   
   
   
   
   
8. Choose the Options for the COM Object as below, then click on Finish.
   
   
   
   
   
9. After these changes, the Calculator.idl file will look like this:
   
   
   
   
   
   
   
   Here, the declaration for interface ICalculator is added. ICalculator implements IDispatch interface. IDispatch is the interface that exposes the OLE Automation protocol. It is one of the standard interfaces exposed by COM. The IDispatch interface inherits from the IUnknown interface. More information on IDispatch can be found here. You can also see the declaration of the Type Library CalculatorLib which declares a coclass Calculator as well. This CoClass creates a COM object, which can implement a COM interface. The Type library information helps in creating .tlb file which is a binary file that stores information about a COM or DCOM object's properties and methods in a form that is accessible to other applications at runtime. Using a type library, an application or browser can determine which interfaces an object supports, and invoke an object's interface methods. This can occur even if the object and client applications were written in different programming languages. The COM/DCOM run-time environment can also use a type library to provide automatic cross-apartment, cross-process, and cross-machine marshaling for interfaces described in type libraries.
   
10. Now our interface is ready to have some methods. Switch to Class View beside Solution Explorer as shown in image below. Right click on ICalculator interface and add a method. Add->Add Method.
    
    
    
11. Give the method name as Add , check parameter attributes as 'in', parameter type DOUBLE, parameter name as Input1. Click on Add. You should see the parameter being added to the list box. Similarly add one more input parameter named Input2. Now add an output parameter with parameter type DOUBLE*, parameter name as pOutput, check parameter attributes as 'out' and 'retval'. Click on Add. Click on Next->Finish.
    
    
    
    
    
    
    
    
    
    
    Similarly add three more methods Subtract, Multiply and Divide.
    
    
12. After adding the methods , you should see the functions' skeleton created in Calculator.idl and CalculatorImpl.cpp like this :
    
    
    
    
    
    
13. We will add the implementation in the skeleton.
14. Now compile the solution. It will generate Calculator.dll in the project output directory (e.g. for 64 bit Release configuration it is %PROJECT_HOME%\Calculator\Calculator\x64\Release by default)

Now we have our COM DLL. To use it , we need some code.

Steps to create sample C++ code to test COM DLL:

1. Create an Empty Win32 Console Project in Visual Studio
   
   
   
   
   
2. Create an Empty cpp file in the project (TestCalc.cpp)
   
   
   
   
   
3. Add the path to Calculator.h in Additional Include Directories in the project properties. Right click project -> Properties -> Configuration Properties -> C/C++ -> General.
   
   
   
   
   
4. Add Calculator_i.c in the Project Source.
   
   
   
   
   
5. Populate TestCalc.cpp with the contents given later in the blog post.
6. Run the executable(F5).

Note: One advantage using the Visual Studio to build our COM dll was that it registers the COM DLL by default. So we do not need to do it manually. This is the reason why we are able to run the test code even without the DLL being present in the System Path or adding it's path to PATH environment variable .

Now as we have been saying that the COM is interoperable between the languages/platform etc. Let's see some code in action.
We are going to use the COM DLL generated in C# application.

Before we go on using DLLs directly , let's be SMART and create .NET wrappers over COM DLL. Now you would ask what's that ??

The COM components has unmanaged code while .NET framework has managed code. Data types, method signatures, and error-handling mechanisms vary between managed and unmanaged object models
Code that executes under the control of the runtime is called managed code and the code that runs outside the runtime is called unmanaged code.

To simplify this, .NET wrappers are generated over existing COM components which allows unmanaged model to be converted to managed.
More information in this link.

Steps to create .NET wrapper from COM DLL:

Run this command from the output directory:

     tlbimp /machine: x64 Calculator.dll /out: Calculator_Wrapper.dll

It will generate Calculator_Wrapper.dll which is nothing but our .NET wrapper over COM.

Steps to create C# application to test COM DLL :

1. Create a Windows Application TestCalcCCharp from Visual Studio
   
   
   
   
   
2. Add a reference to the wrapper Calculator_Wrapper.dll
   
   
   
   
   
3. Create a simple form as per the code in the blog post.
   
   
   
   
   
4. Populate the functions to call the methods from COM.

// CalculatorImpl.cpp : Implementation of CCalculatorImpl

#include "stdafx.h"
#include "CalculatorImpl.h"

// CCalculatorImpl

STDMETHODIMP CCalculatorImpl::Add(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 + Input2;

 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Subtract(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 - Input2;
 
 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Multiply(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 * Input2;

 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Divide(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 / Input2;

 return S_OK;
}

//TestCalc.cpp
#include "Calculator.h"
#include <iostream>
#include <stdexcept>
using std::runtime_error; 

int main()
{
 HRESULT hr ;
 ICalculator      *calc = NULL;

 hr = CoInitialize(0);

 if(SUCCEEDED(hr))
    {
  hr = CoCreateInstance( CLSID_Calculator, NULL, 
            CLSCTX_INPROC_SERVER,
   IID_ICalculator, (void**) &calc);

        // If we succeeded then call the Add 
        // method, if it failed
        // then display an appropriate message to the user.
        if(SUCCEEDED(hr))
        {
            double ReturnValue;
   double a = 4;
   double b = 0;
   calc->Add(a, b, &ReturnValue);
            std::cout << "The answer for "<<a<<" + "<<b<<" is: " 
                << ReturnValue << std::endl;
            calc->Release(); 
        }
        else
        {
            std::cout << "CoCreateInstance Failed." << std::endl;
        }
    }
    // Uninitialize COM
    CoUninitialize();

}

//Form1.Designer.cs
namespace TestCalcCSharp
{
    partial class Form1
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.calcPanel = new System.Windows.Forms.GroupBox();
            this.groupBox1 = new System.Windows.Forms.GroupBox();
            this.logTextBox = new System.Windows.Forms.RichTextBox();
            this.label5 = new System.Windows.Forms.Label();
            this.label4 = new System.Windows.Forms.Label();
            this.label1 = new System.Windows.Forms.Label();
            this.divBtn = new System.Windows.Forms.Button();
            this.subBtn = new System.Windows.Forms.Button();
            this.addBtn = new System.Windows.Forms.Button();
            this.mulBtn = new System.Windows.Forms.Button();
            this.textBox3 = new System.Windows.Forms.TextBox();
            this.textBox2 = new System.Windows.Forms.TextBox();
            this.label3 = new System.Windows.Forms.Label();
            this.label2 = new System.Windows.Forms.Label();
            this.textBox1 = new System.Windows.Forms.TextBox();
            this.calcPanel.SuspendLayout();
            this.groupBox1.SuspendLayout();
            this.SuspendLayout();
            // 
            // calcPanel
            // 
            this.calcPanel.Controls.Add(this.groupBox1);
            this.calcPanel.Controls.Add(this.label5);
            this.calcPanel.Controls.Add(this.label4);
            this.calcPanel.Controls.Add(this.label1);
            this.calcPanel.Controls.Add(this.divBtn);
            this.calcPanel.Controls.Add(this.subBtn);
            this.calcPanel.Controls.Add(this.addBtn);
            this.calcPanel.Controls.Add(this.mulBtn);
            this.calcPanel.Controls.Add(this.textBox3);
            this.calcPanel.Controls.Add(this.textBox2);
            this.calcPanel.Controls.Add(this.label3);
            this.calcPanel.Controls.Add(this.label2);
            this.calcPanel.Controls.Add(this.textBox1);
            this.calcPanel.Location = new System.Drawing.Point(13, 13);
            this.calcPanel.Name = "calcPanel";
            this.calcPanel.Size = new System.Drawing.Size(450, 344);
            this.calcPanel.TabIndex = 0;
            this.calcPanel.TabStop = false;
            this.calcPanel.Text = "Calculator";
            // 
            // groupBox1
            // 
            this.groupBox1.Controls.Add(this.logTextBox);
            this.groupBox1.Location = new System.Drawing.Point(6, 238);
            this.groupBox1.Name = "groupBox1";
            this.groupBox1.Size = new System.Drawing.Size(438, 100);
            this.groupBox1.TabIndex = 34;
            this.groupBox1.TabStop = false;
            this.groupBox1.Text = "Logs";
            // 
            // logTextBox
            // 
            this.logTextBox.Location = new System.Drawing.Point(6, 19);
            this.logTextBox.Name = "logTextBox";
            this.logTextBox.Size = new System.Drawing.Size(432, 81);
            this.logTextBox.TabIndex = 33;
            this.logTextBox.Text = "";
            // 
            // label5
            // 
            this.label5.AutoSize = true;
            this.label5.Location = new System.Drawing.Point(254, 22);
            this.label5.Name = "label5";
            this.label5.Size = new System.Drawing.Size(37, 13);
            this.label5.TabIndex = 32;
            this.label5.Text = "Result";
            // 
            // label4
            // 
            this.label4.AutoSize = true;
            this.label4.Location = new System.Drawing.Point(163, 22);
            this.label4.Name = "label4";
            this.label4.Size = new System.Drawing.Size(37, 13);
            this.label4.TabIndex = 31;
            this.label4.Text = "Input2";
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(83, 22);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(37, 13);
            this.label1.TabIndex = 30;
            this.label1.Text = "Input1";
            // 
            // divBtn
            // 
            this.divBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.divBtn.Location = new System.Drawing.Point(352, 134);
            this.divBtn.Name = "divBtn";
            this.divBtn.Size = new System.Drawing.Size(75, 36);
            this.divBtn.TabIndex = 29;
            this.divBtn.Text = "Divide";
            this.divBtn.UseVisualStyleBackColor = true;
            this.divBtn.Click += new System.EventHandler(this.divBtn_Click);
            // 
            // subBtn
            // 
            this.subBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.subBtn.Location = new System.Drawing.Point(125, 134);
            this.subBtn.Name = "subBtn";
            this.subBtn.Size = new System.Drawing.Size(75, 36);
            this.subBtn.TabIndex = 28;
            this.subBtn.Text = "Subtract";
            this.subBtn.UseVisualStyleBackColor = true;
            this.subBtn.Click += new System.EventHandler(this.subBtn_Click);
            // 
            // addBtn
            // 
            this.addBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.addBtn.Location = new System.Drawing.Point(14, 134);
            this.addBtn.Name = "addBtn";
            this.addBtn.Size = new System.Drawing.Size(75, 36);
            this.addBtn.TabIndex = 27;
            this.addBtn.Text = "Add";
            this.addBtn.UseVisualStyleBackColor = true;
            this.addBtn.Click += new System.EventHandler(this.addBtn_Click);
            // 
            // mulBtn
            // 
            this.mulBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.mulBtn.Location = new System.Drawing.Point(239, 134);
            this.mulBtn.Name = "mulBtn";
            this.mulBtn.Size = new System.Drawing.Size(75, 36);
            this.mulBtn.TabIndex = 26;
            this.mulBtn.Text = "Multiply";
            this.mulBtn.UseVisualStyleBackColor = true;
            this.mulBtn.Click += new System.EventHandler(this.mulBtn_Click);
            // 
            // textBox3
            // 
            this.textBox3.Enabled = false;
            this.textBox3.Location = new System.Drawing.Point(257, 41);
            this.textBox3.Name = "textBox3";
            this.textBox3.Size = new System.Drawing.Size(170, 20);
            this.textBox3.TabIndex = 7;
            // 
            // textBox2
            // 
            this.textBox2.Location = new System.Drawing.Point(166, 41);
            this.textBox2.Name = "textBox2";
            this.textBox2.Size = new System.Drawing.Size(57, 20);
            this.textBox2.TabIndex = 6;
            // 
            // label3
            // 
            this.label3.AutoSize = true;
            this.label3.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.label3.Location = new System.Drawing.Point(228, 44);
            this.label3.Name = "label3";
            this.label3.Size = new System.Drawing.Size(16, 17);
            this.label3.TabIndex = 4;
            this.label3.Text = "=";
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.label2.Location = new System.Drawing.Point(146, 44);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(16, 17);
            this.label2.TabIndex = 3;
            this.label2.Text = "+";
            // 
            // textBox1
            // 
            this.textBox1.Location = new System.Drawing.Point(83, 41);
            this.textBox1.Name = "textBox1";
            this.textBox1.Size = new System.Drawing.Size(57, 20);
            this.textBox1.TabIndex = 1;
            // 
            // Form1
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(475, 369);
            this.Controls.Add(this.calcPanel);
            this.Name = "Form1";
            this.Text = "Calculator";
            this.calcPanel.ResumeLayout(false);
            this.calcPanel.PerformLayout();
            this.groupBox1.ResumeLayout(false);
            this.ResumeLayout(false);

        }

        #endregion

        private System.Windows.Forms.GroupBox calcPanel;
        private System.Windows.Forms.TextBox textBox1;
        private System.Windows.Forms.TextBox textBox3;
        private System.Windows.Forms.TextBox textBox2;
        private System.Windows.Forms.Label label3;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.Button mulBtn;
        private System.Windows.Forms.Button divBtn;
        private System.Windows.Forms.Button subBtn;
        private System.Windows.Forms.Button addBtn;
        private System.Windows.Forms.Label label5;
        private System.Windows.Forms.Label label4;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.RichTextBox logTextBox;
        private System.Windows.Forms.GroupBox groupBox1;

    }
}

//Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using Calculator_Wrapper;
using System.Runtime.InteropServices;

namespace TestCalcCSharp
{
    public partial class Form1 : Form
    {
        Calculator_Wrapper.Calculator calc = null;

        public Form1()
        {
            InitializeComponent();
            calc = new Calculator();
        }

        private void addBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);


                double output = calc.Add(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void subBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);


                double output = calc.Subtract(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void mulBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);

                double output = calc.Multiply(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void divBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);

                if (inp2 == 0) throw new DivideByZeroException();
                double output = calc.Divide(inp1, inp2);
                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message + "\n";
            }
        }
    }
}