import java.util.HashSet;
public class LCS {
private int [][] LCS_Matrix(String oldStr, String newStr) {
int m[][] = new int[oldStr.length() + 1][newStr.length() + 1];
for (int i = 1; i <= oldStr.length(); i++) {
for (int j = 1; j <= newStr.length(); j++) {
char c1 = oldStr.charAt(i - 1);
char c2 = newStr.charAt(j - 1);
if (c1 == c2) {
m[i][j] = m[i - 1][j - 1] + 1;
} else {
m[i][j] = Math.max(m[i - 1][j], m[i][j - 1]);
}
}
}
return m;
}
private HashSet<String> backTraceAll(int[][] m, String oldStr, String newStr, int i, int j) {
if (i == 0 || j == 0) {
HashSet<String> a = new HashSet<>();
a.add("");
return a;
} else if (oldStr.charAt(i - 1) == newStr.charAt(j - 1)) {
HashSet<String> a = new HashSet<>();
HashSet<String> b = backTraceAll(m, oldStr, newStr, i - 1, j - 1);
for (String g : b) {
a.add(g + oldStr.charAt(i - 1));
}
return a;
} else {
HashSet<String> a = new HashSet<>();
if (m[i][j - 1] >= m[i - 1][j])
a.addAll(backTraceAll(m, oldStr, newStr, i, j - 1));
if (m[i - 1][j] >= m[i][j - 1])
a.addAll(backTraceAll(m, oldStr, newStr, i - 1, j));
return a;
}
}
public void process(String oldStr, String newStr) {
int [][] LCSMatrix = LCS_Matrix(oldStr, newStr);
HashSet<String> hs = backTraceAll(LCSMatrix, oldStr, newStr, oldStr.length(), newStr.length());
System.out.println("List of Longest Common Subsequence:");
for(String s : hs)
System.out.println(s);
}
public static void main(String[] args) {
new LCS().process("abc512238gh", "abc523278gh");
}
}
Category Archives: Algorithms
BTree in Java
btreeNode.java
import java.util.Vector;
public class btreeNode {
private Vector<Integer> values = new Vector<>();
private Vector<btreeNode> nodes = new Vector<>();
private btreeNode parent = null;
public btreeNode() {
}
public btreeNode(btreeNode p, Vector<Integer> v, Vector<btreeNode> vb) {
parent = p;
values = v;
nodes = vb;
vb.forEach(x -> x.parent = this);
}
btreeNode findNodeToInsert(int v) {
if (isNodeALeaf())
return this;
if (nodes.size() > 0) {
if (v < values.firstElement()) {
return nodes.firstElement().findNodeToInsert(v);
} else if (v > values.lastElement()) {
return nodes.lastElement().findNodeToInsert(v);
} else {
for (int i = 0; i < values.size() - 1; i++) {
if (v > values.elementAt(i) && v < values.elementAt(i + 1)) {
return nodes.elementAt(i + 1).findNodeToInsert(v);
}
}
}
}
return null;
}
btreeNode traverseRight() {
if(isNodeALeaf()) {
return this;
}
return nodes.lastElement().traverseRight();
}
btreeNode findNodeValue(int v) {
for (int i = 0; i < values.size(); i++) {
if (v == values.elementAt(i))
return this;
if (isNodeALeaf())
continue;
if (v < values.firstElement()) {
return nodes.firstElement().findNodeValue(v);
} else if (v > values.lastElement()) {
return nodes.lastElement().findNodeValue(v);
} else if (i + 1 < values.size() &&
v > values.elementAt(i) &&
v < values.elementAt(i + 1)) {
return nodes.elementAt(i + 1).findNodeValue(v);
}
}
return null;
}
public boolean findValue(int v) {
return findNodeValue(v) != null ? true : false;
}
void overflow() throws Exception {
if (values.size() < 5)
return;
if (values.size() >= 5) {
splitNode();
if (parent != null) {
parent.insert(values.firstElement());
int index = parent.getIndexOfNode(this);
if (index < 0)
throw new Exception("Index is out of bound");
parent.removeNode(index);
parent.addAllNodes(index, nodes);
nodes.forEach(x -> x.parent = parent);
}
}
if (parent != null) {
parent.overflow();
}
}
void transferNodeFromLeft(int i, btreeNode leftNode) {
int val1 = parent.valueAt(i - 1);
values.add(0, val1);
int val2 = leftNode.getLastValue();
leftNode.removeLastValue();
parent.setValueAt(i - 1, val2);
if(parent.nodeAt(i - 1).isNodeALeaf() == false) {
btreeNode node1 = parent.nodeAt(i - 1).removeLastNode();
nodes.add(0, node1);
node1.parent = this;
}
}
void transferNodeFromRight(int i, btreeNode rightNode) {
int val1 = parent.valueAt(i);
values.add(val1);
int val2 = rightNode.removeFirstValue();
parent.setValueAt(i, val2);
if(parent.nodeAt(i + 1).isNodeALeaf() == false) {
btreeNode node1 = parent.nodeAt(i + 1).removeFirstNode();
nodes.add(node1);
node1.parent = this;
}
}
void mergeNodeToLeft(int i, btreeNode leftNode) {
int val = parent.removeValue(i - 1);
parent.removeNode(this);
values.add(0, val);
leftNode.mergeNodes(this);
}
void mergeNodeToRight(int i, btreeNode rightNode) {
int val = parent.removeValue(i);
parent.removeNode(rightNode);
values.add(val);
mergeNodes(rightNode);
}
void underflow() throws Exception {
if(parent == null)
return;
if(values.size() > 1)
return;
int i = parent.getIndexOfNode(this);
if (i < 0)
throw new Exception("Index is out of bound");
if (i == 0) {
btreeNode rightNode = parent.nodeAt(i + 1);
int rightSize = rightNode.valueSize();
if(rightSize == 2) {
mergeNodeToRight(i, rightNode);
setRoot();
}
else {
transferNodeFromRight(i, rightNode);
}
}
else if(i == parent.nodeSize() - 1) {
btreeNode leftNode = parent.nodeAt(i - 1);
int leftSize = leftNode.valueSize();
if(leftSize == 2) {
mergeNodeToLeft(i, leftNode);
leftNode.setRoot();
}
else {
transferNodeFromLeft(i, leftNode);
}
}
else {
btreeNode leftNode = parent.nodeAt(i - 1);
btreeNode rightNode = parent.nodeAt(i + 1);
int leftSize = leftNode.valueSize();
int rightSize = rightNode.valueSize();
if (leftSize > rightSize) {
transferNodeFromLeft(i, leftNode);
} else if (leftSize < rightSize) {
transferNodeFromRight(i, rightNode);
} else {
mergeNodeToLeft(i, leftNode);
}
}
if(parent != null && parent.valueSize() == 1)
parent.underflow();
}
void setRoot() {
if(parent.valueSize() == 0) {
parent.values = values;
parent.nodes = nodes;
nodes.forEach(x -> x.parent = parent);
parent.parent = null;
}
}
void mergeNodes(btreeNode n2) {
values.addAll(n2.values);
nodes.addAll(n2.nodes);
nodes.forEach(x -> x.parent = this);
}
public void insert(int v) {
int i = 0;
for (; i < values.size(); i++) {
if (values.elementAt(i) > v) {
break;
}
}
values.add(i, v);
}
public void splitNode() {
Vector<Integer> leftValues = new Vector<>(values.subList(0, values.size() / 2));
Vector<Integer> rightValues = new Vector<>(values.subList(values.size() / 2 + 1, values.size()));
Vector<btreeNode> leftNodes = new Vector<>(nodes.subList(0, nodes.size() / 2));
Vector<btreeNode> rightNodes = new Vector<>(nodes.subList(nodes.size() / 2, nodes.size()));
int midVal = values.elementAt(values.size() / 2);
btreeNode leftNode = new btreeNode(this, leftValues, leftNodes);
btreeNode rightNode = new btreeNode(this, rightValues, rightNodes);
values.clear();
nodes.clear();
values.add(midVal);
nodes.add(leftNode);
nodes.add(rightNode);
}
Vector<btreeNode> getNodes() {
return nodes;
}
int getIndexOfNode(btreeNode n) {
return nodes.indexOf(n);
}
int getIndexOfValue(int n) {
return values.indexOf(n);
}
int removeValue(int index) {
return values.remove(index);
}
int removeLastValue() {
return values.remove(values.size() - 1);
}
int removeFirstValue() {
return values.remove(0);
}
btreeNode removeNode(int index) {
return nodes.remove(index);
}
void removeNode(btreeNode n) {
nodes.remove(n);
}
btreeNode removeLastNode() {
return nodes.remove(nodes.size() - 1);
}
btreeNode removeFirstNode() {
return nodes.remove(0);
}
void addAllNodes(int index, Vector<btreeNode> n) {
nodes.addAll(index, n);
}
btreeNode nodeAt(int index) {
return nodes.elementAt(index);
}
int valueAt(int index) {
return values.elementAt(index);
}
void setValueAt(int index, int n) {
values.set(index, n);
}
int valueSize() {
return values.size();
}
int nodeSize() {
return nodes.size();
}
int getLastValue() {
return values.lastElement();
}
btreeNode getParent() {
return parent;
}
boolean isNodeALeaf() {
return nodes.isEmpty();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.size(); i++)
sb.append(values.elementAt(i) + ", ");
sb.deleteCharAt(sb.length() - 1);
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
}
btree.java
import java.util.HashMap;
import java.util.Set;
import java.util.Vector;
public class btree {
btreeNode root = new btreeNode();
void insert(int v) throws Exception {
btreeNode node = root.findNodeToInsert(v);
node.insert(v);
node.overflow();
}
boolean find(int v) {
return root.findValue(v);
}
void delete(int v) throws Exception {
btreeNode n = root.findNodeValue(v);
if(n == null)
return;
int i = n.getIndexOfValue(v);
if(n.isNodeALeaf()) {
n.removeValue(i);
n.underflow();
}
else {
btreeNode lastRight = n.nodeAt(i).traverseRight();
int lastRightVal = lastRight.getLastValue();
lastRight.removeLastValue();
n.setValueAt(i, lastRightVal);
lastRight.underflow();
}
}
void debugStr(int level, btreeNode n, HashMap<Integer, Vector<String>> h) {
Vector<String> s1 = h.get(level);
if (s1 == null) {
s1 = new Vector<>();
h.put(level, s1);
}
s1.add(n.toString() + " (" + n.getParent() + ")");
for (int i = 0; i < n.getNodes().size(); i++) {
debugStr(level + 1, n.getNodes().elementAt(i), h);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
HashMap<Integer, Vector<String>> disp1 = new HashMap<>();
debugStr(1, root, disp1);
Set<Integer> keys = disp1.keySet();
for (Integer i : keys) {
Vector<String> v = disp1.get(i);
v.forEach((String str) -> sb.append(str + " | "));
sb.append("\n");
}
return sb.toString();
}
}
Depth-first search algorithm in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DepthFirst
{
class Program
{
public class Person
{
public Person(string name)
{
this.name = name;
}
public string name { get; set; }
public List<Person> Friends
{
get
{
return FriendsList;
}
}
public void isFriendOf(Person p)
{
FriendsList.Add(p);
}
List<Person> FriendsList = new List<Person>();
public override string ToString()
{
return name;
}
}
public class DepthFirstAlgorithm
{
public Person BuildFriendGraph()
{
Person Aaron = new Person("Aaron");
Person Betty = new Person("Betty");
Person Brian = new Person("Brian");
Aaron.isFriendOf(Betty);
Aaron.isFriendOf(Brian);
Person Catherine = new Person("Catherine");
Person Carson = new Person("Carson");
Person Darian = new Person("Darian");
Person Derek = new Person("Derek");
Betty.isFriendOf(Catherine);
Betty.isFriendOf(Darian);
Brian.isFriendOf(Carson);
Brian.isFriendOf(Derek);
return Aaron;
}
public Person Search(Person root, string nameToSearchFor)
{
if (nameToSearchFor == root.name)
return root;
Person personFound = null;
for (int i = 0; i < root.Friends.Count; i++)
{
personFound = Search(root.Friends[i], nameToSearchFor);
if (personFound != null)
break;
}
return personFound;
}
public void Traverse(Person root)
{
Console.WriteLine(root.name);
for (int i = 0; i < root.Friends.Count; i++)
{
Traverse(root.Friends[i]);
}
}
}
static void Main(string[] args)
{
DepthFirstAlgorithm b = new DepthFirstAlgorithm();
Person root = b.BuildFriendGraph();
Console.WriteLine("Traverse\n------");
b.Traverse(root);
Console.WriteLine("\nSearch\n------");
Person p = b.Search(root, "Catherine");
Console.WriteLine(p == null ? "Person not found" : p.name);
p = b.Search(root, "Alex");
Console.WriteLine(p == null ? "Person not found" : p.name);
}
}
}
Kadane’s (Maximum Subarray) Algorithm
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
//http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
static int MaxSubArray_wiki(int[] arr)
{
int max_ending_here = 0;
int max_so_far = 0;
foreach (int x in arr)
{
max_ending_here = Math.Max(0, max_ending_here + x);
max_so_far = Math.Max(max_so_far, max_ending_here);
}
return max_so_far;
}
static int MaxSubArray(int[] arr)
{
int max_ending_here = 0;
int max_so_far = 0;
for (int i = 0; i < arr.Length; i++)
{
int x = arr[i];
max_ending_here += x;
if (max_ending_here <= 0)
max_ending_here = 0;
if (max_ending_here > max_so_far)
max_so_far = max_ending_here;
}
return max_so_far;
}
static void Main(string[] args)
{
int[] arr = { 3, 4, -6, 33, 45, 55, -10, 1000, -2000, 5, 6, 1490 };
Console.WriteLine(MaxSubArray(arr));
Console.WriteLine(MaxSubArray_wiki(arr));
}
}
Breadth-first search algorithm in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BreadthFirst
{
class Program
{
public class Person
{
public Person(string name)
{
this.name = name;
}
public string name { get; set; }
public List<Person> Friends
{
get
{
return FriendsList;
}
}
public void isFriendOf(Person p)
{
FriendsList.Add(p);
}
List<Person> FriendsList = new List<Person>();
public override string ToString()
{
return name;
}
}
public class BreadthFirstAlgorithm
{
public Person BuildFriendGraph()
{
Person Aaron = new Person("Aaron");
Person Betty = new Person("Betty");
Person Brian = new Person("Brian");
Aaron.isFriendOf(Betty);
Aaron.isFriendOf(Brian);
Person Catherine = new Person("Catherine");
Person Carson = new Person("Carson");
Person Darian = new Person("Darian");
Person Derek = new Person("Derek");
Betty.isFriendOf(Catherine);
Betty.isFriendOf(Darian);
Brian.isFriendOf(Carson);
Brian.isFriendOf(Derek);
return Aaron;
}
//http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode
public Person Search(Person root, string nameToSearchFor)
{
Queue<Person> Q = new Queue<Person>();
HashSet<Person> S = new HashSet<Person>();
Q.Enqueue(root);
S.Add(root);
while (Q.Count > 0)
{
Person p = Q.Dequeue();
if (p.name == nameToSearchFor)
return p;
foreach (Person friend in p.Friends)
{
if (!S.Contains(friend))
{
Q.Enqueue(friend);
S.Add(friend);
}
}
}
return null;
}
public void Traverse(Person root)
{
Queue<Person> traverseOrder = new Queue<Person>();
Queue<Person> Q = new Queue<Person>();
HashSet<Person> S = new HashSet<Person>();
Q.Enqueue(root);
S.Add(root);
while (Q.Count > 0)
{
Person p = Q.Dequeue();
traverseOrder.Enqueue(p);
foreach (Person friend in p.Friends)
{
if (!S.Contains(friend))
{
Q.Enqueue(friend);
S.Add(friend);
}
}
}
while (traverseOrder.Count > 0)
{
Person p = traverseOrder.Dequeue();
Console.WriteLine(p);
}
}
}
static void Main(string[] args)
{
BreadthFirstAlgorithm b = new BreadthFirstAlgorithm();
Person root = b.BuildFriendGraph();
Console.WriteLine("Traverse\n------");
b.Traverse(root);
Console.WriteLine("\nSearch\n------");
Person p = b.Search(root, "Catherine");
Console.WriteLine(p == null ? "Person not found" : p.name);
p = b.Search(root, "Alex");
Console.WriteLine(p == null ? "Person not found" : p.name);
}
}
}
Kruskal’s algorithm
Solution to problem 107 @ Project Euler. Implemented using Kruskal’s algorithm.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace problem107
{
class Program
{
class Vertex
{
public Vertex(int index)
{
this.index = index;
}
public int index;
public override bool Equals(object obj)
{
return index == ((Vertex)obj).index;
}
public override int GetHashCode()
{
return index;
}
public override string ToString()
{
return index.ToString();
}
}
class Edge
{
public Edge(int weight, Vertex v1, Vertex v2)
{
this.weight = weight;
this.v1 = v1;
this.v2 = v2;
}
public int weight;
public Vertex v1;
public Vertex v2;
public override bool Equals(object obj)
{
Edge e2 = (Edge)obj;
return (this.v1.Equals(e2.v1) && this.v2.Equals(e2.v2))||
(this.v2.Equals(e2.v1) && this.v1.Equals(e2.v2));
}
public override int GetHashCode()
{
return weight;
}
public override string ToString()
{
return "" + v1.index + "-" + v2.index;
}
public static int compareByWeight(Edge e1, Edge e2)
{
if (e1.weight < e2.weight)
return -1;
else if (e1.weight > e2.weight)
return 1;
else
return 0;
}
}
class Tree
{
public List<Vertex> vertices = new List<Vertex>();
public List<Edge> edges = new List<Edge>();
public static Tree Merge(Tree t1, Tree t2, Edge e)
{
Tree newTree = new Tree();
newTree.vertices.AddRange(t1.vertices);
newTree.vertices.AddRange(t2.vertices);
newTree.edges.AddRange(t1.edges);
newTree.edges.AddRange(t2.edges);
newTree.edges.Add(e);
return newTree;
}
}
class Forest
{
public List<Tree> trees = new List<Tree>();
}
static List<Vertex> createVertices(int n)
{
List<Vertex> v = new List<Vertex>();
for (int i = 0; i < n; i++)
{
v.Add(new Vertex(i));
}
return v;
}
//http://en.wikipedia.org/wiki/Kruskal%27s_algorithm#Description
static void solve()
{
string[] lines = System.IO.File.ReadAllLines(@"network.txt");
//create a forest
Forest F = new Forest();
//create a list of vertices
List<Vertex> vertices = createVertices(lines.Length);
//each vertex is a tree in a forest
foreach (Vertex v in vertices)
{
Tree t1 = new Tree();
t1.vertices.Add(v);
F.trees.Add(t1);
}
//create a list of all edges
List<Edge> S = new List<Edge>();
for (int i = 0; i < lines.Length; i++)
{
//find vertex to one end
Vertex v1 = vertices.Find(x => x.index == i);
string[] e = lines[i].Split(',');
for (int j = 0; j < e.Length; j++)
{
if (e[j] != "-")
{
//find vertex to the other end
Vertex v2 = vertices.Find(x => x.index == j);
//create the edge
Edge edge = new Edge(Convert.ToInt32(e[j]), v1, v2);
//try to find the edge in the list
Edge temp = S.Find(x => x.Equals(edge));
//if not found, add the add to the list
if (temp == null)
S.Add(edge);
}
}
}
//sort them by weight. smallest weight first
S.Sort(Edge.compareByWeight);
int sumBeforeMininized = S.Sum(x => x.weight);
int count = 0;
while (S.Count > 0)
{
//get the first edge from the list
Edge e = S[count];
//remove the edge
S.Remove(e);
//find the trees that contains the vertices in edge e
Tree t1 = F.trees.Find(x => x.vertices.Find(y => y.Equals(e.v1)) != null);
Tree t2 = F.trees.Find(x => x.vertices.Find(y => y.Equals(e.v2)) != null);
//if the 2 trees found are the same, ignore
if (t1 == t2)
continue;
//Merge the two tress together by creating a new tree
//then adding all the vertices and edges including
//edge e
Tree tFinal = Tree.Merge(t1, t2, e);
//remove the 2 trees from the forest and add the new merged tree
F.trees.Remove(t1);
F.trees.Remove(t2);
F.trees.Add(tFinal);
}
int sumAfterMininized = F.trees[0].edges.Sum(x => x.weight);
Console.WriteLine(sumBeforeMininized - sumAfterMininized);
}
static void Main(string[] args)
{
solve();
}
}
}
Dijkstra’s algorithm
Solution to Problem 83 on Project Euler. Solution implemented using Dijkstra’s shortest path algorithm.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace problem83
{
class Node
{
public Node(int value, int x, int y)
{
this.value = value;
this.x = x;
this.y = y;
}
public int value;
public int x;
public int y;
public override string ToString()
{
return value + " " + x + " " + y;
}
}
class Program
{
static int size = 80;
static public Node[,] grid = new Node[size, size];
static public List<Node> ListOfNodes = new List<Node>();
static void generateGrid()
{
string[] lines = System.IO.File.ReadAllLines(@"matrix.txt");
size = lines.Length;
grid = new Node[size, size];
for (int i = 0; i < lines.Length; i++)
{
string[] s = lines[i].Split(',');
for (int j = 0; j < s.Length; j++)
{
grid[j, i] = new Node(Convert.ToInt32(s[j]), j, i);
ListOfNodes.Add(grid[j, i]);
}
}
}
static Node findSmallestDistance(Hashtable dist, List<Node> Q)
{
int distance = int.MaxValue;
Node node = null;
foreach (Node n in Q)
{
if ((int)dist[n] < distance)
{
distance = (int)dist[n];
node = n;
}
}
return node;
}
static Node[] findNeighbor(Node n)
{
List<Node> neighbor = new List<Node>();
int x = n.x;
int y = n.y;
if (x + 1 < size)
neighbor.Add(grid[x + 1, y]);
if (x - 1 >= 0)
neighbor.Add(grid[x - 1, y]);
if (y + 1 < size)
neighbor.Add(grid[x, y + 1]);
if (y - 1 >= 0)
neighbor.Add(grid[x, y - 1]);
return neighbor.ToArray<Node>();
}
static void Dijkstra()
{
//hashtable to store the sum (or distance)
Hashtable dist = new Hashtable();
//List to store all the nodes
List<Node> Q = new List<Node>();
for (int y = 0; y < size; y++)
{
for (int x = 0; x < size; x++)
{
Node n = grid[x, y];
//set node as key and value to infinity (or int max)
//because all sum (or distance) is infinity
dist[n] = int.MaxValue;
//add node to list
Q.Add(n);
}
}
//set the first sum to the first value in the grid
dist[grid[0, 0]] = grid[0, 0].value;
while (Q.Count > 0)
{
//find the node with the smallest sum (or shortest distance)
Node u = findSmallestDistance(dist, Q);
//remove it from the list Q
Q.Remove(u);
//if the smallest sum (or distance) is infinity
//then no need to continue
if ((int)dist[u] == int.MaxValue)
break;
//locate the neighbors in the grid
Node[] neighbors = findNeighbor(u);
foreach (Node v in neighbors)
{
//add the neighbor's value to the sum (or distance) of current node.
int alt = (int)dist[u] + v.value;
//if the value is smaller, replace that value
if (alt < (int)dist[v])
{
dist[v] = alt;
}
}
}
Console.WriteLine(dist[grid[size - 1, size - 1]]);
}
static void solve()
{
generateGrid();
Dijkstra();
}
static void Main(string[] args)
{
solve();
}
}
}
Random Code Generator 