Skip to content

Instantly share code, notes, and snippets.

View aaani's full-sized avatar

Ani Mishra aaani

View GitHub Profile
@aaani
aaani / ManachersAlgorithm.cpp
Last active December 19, 2015 17:09
Manacher's algorithm is used to find longest palindrome substring in a string. The worst case time complexity of this algorithm is O(n) and space complexity is also O(n) where n is the length of input string. Note that extend() and mirror() need not to be separate methods and could be done in single pass, but I have separated them on purpose to …
// Mancher.cpp
//
// Created by Anirvana Mishra on 6/30/13.
// Copyright (c) 2013 Anirvana Mishra. All rights reserved.
// Code is inspired by the algorithm explained here: http://wcipeg.com/wiki/index.php?title=Longest_palindromic_substring
#include <iostream>
#include <vector>
using namespace std;
@aaani
aaani / N-wayMerge.cpp
Last active December 19, 2015 17:09
Here is an implementation for N-way merge using priority queue data structure. Code requires n sorted vector<int> as input and generates one huge vector containing the result of merge of input vectors. The worst case time complexity of this algorithm is O(m * log(m)) where m is the total number of elements in all the lists.
// MergeK
//
// Created by Anirvana Mishra on 6/18/13.
// Copyright (c) 2013 Anirvana Mishra. All rights reserved.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
@aaani
aaani / Newton-Raphson.cpp
Last active December 19, 2015 17:09
Here is an implementation of the Newton-Raphson method for finding square root. Time complexity analysis: http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity
// Newton-Raphson
//
// Created by Anirvana Mishra on 6/29/13.
// Copyright (c) 2013 Anirvana Mishra. All rights reserved.
//
long double sq_root(double x)
{
long double rt = 1, ort = 0;
while(ort!=rt)
{
@aaani
aaani / SuffixArray.cpp
Created July 13, 2013 05:27
Here is an implementation for Suffix array data structure. The method that I have used for creating the suffix array is known as Prefix-doubling which results in a worst time complexity of O(n*log(n)) where n is the length of the input string. Algorithm details and numerous applications could be found here: http://www.stanford.edu/class/cs97si/s…
// SuffixArray
//
// Created by Anirvana Mishra on 7/1/13.
// Copyright (c) 2013 Anirvana Mishra. All rights reserved.
// Code inspired by http://www.stanford.edu/class/cs97si/suffix-array.pdf
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
@aaani
aaani / power.php
Last active December 21, 2015 12:08
PHP implementation for 'Exponentiation by Squaring' method for finding power of a given number. This algorithm runs in O(log(P)) time where P is the power.
function findPower($base, $exponent){
if($exponent==0) return 1;
$output=$base;
$p=1;
while($p*2<$exponent){
$output*=$output;
$p+=$p;
}
@aaani
aaani / QuickSort.java
Last active November 23, 2023 07:56
Here is a Java implementation of randomized quicksort. This is a non-deterministic algorithm with average case time complexity of O(n*log(n)) and worst case space complexity of O(1), where n is the input size. This algorithm is unstable but one can make it stable by giving away O(n) space.
import java.util.*;
/**
*
* @author anirvana
*/
public class QuickSort {
public static void main(String[] args) {
ArrayList<Integer> elements=new ArrayList<Integer>();
@aaani
aaani / MergeSort.java
Last active December 21, 2015 17:08
Here is a Java implementation of merge sort. This algorithms runs in O(n*log(n)) worst case time and O(n) space, where n is the input size. It's a stable sort, commonly used in sorting from disk.
import java.util.ArrayList;
/**
*
* @author anirvana
*/
public class MergeSort {
public static void main(String[] args) {
ArrayList<Integer> elements=new ArrayList<Integer>();
int LCPLength(vector<string> input){
//Find the length of shortest string in the input set
int minLen = INT32_MAX;
for(int i=0;i<input.size();i++){
if(input[i].length()<minLen) minLen=(int)input[i].length();
}
bool done = false;
int lcpLen=0;
int find(vector<int> elements, int start, int end, int key){
if(start>end) return -1;
int mid = start + (end-start)/2;
if(elements[mid]==key) return mid;
if(elements[mid]>=elements[start]){
if(key>=elements[start] && key<elements[mid]) return find(elements,start,mid-1,key);
else return find(elements,mid+1,end,key);
}else{
template<int N>
void rotate90Clockwise(int (&matrix)[N][N]){
//Transpose the matrix
int temp;
for(int i=0;i<N;i++){
for(int j=0;j<i;j++){
temp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=temp;
}