String

### editing distance

edit-distance problem

Suffix tree

### Finding the Minimum Window in S which Contains All Elements from T

Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).

eg,
T = “ABC”

Minimum window is “BANC”.

Finding the Minimum Window in S which Contains All Elements from T

#### Replace all occurrence of the given pattern to ‘X’.

For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

solution: keep a slow and a fast pointer.

Replace all occurrence of the given pattern to ‘X’

#### Kadane's Algorithm Largest sum sub-sequence and sub-matrix

1. Problem 1 : Given a sequence of n integers ( +ve and/or -ve ) find a contiguous subsequence with the largest sum. By contiguous subsequence I mean if the i-th element and j-th element of the original sequence are in the subsequence for ( i \leq j ) then \forall k, i \leq k \leq j k-th element is in the subsequence.

Example : sequence : 1 5 -9 2 4 3 8

desired subsequence : 2 4 3 8

http://wordaligned.org/articles/the-maximum-subsequence-problem

if empty subsequence is not accounted as 0.

void kadane(int input[], int n, int &x1, int &x2, int &max)
{
int cur, i;
max = 0;
cur = 0;
x1 = x2 = 0;
int lx1, lx2;
lx1 = 0;
for(int i = 0; i<n; i++)
{
cur = cur+input[i];
if(cur > max)
{
max = cur;
x2 = i;
x1 = lx1;
}
if (cur < 0)
{
cur = 0;
lx1 = i + 1;
}
}
}

1. Problem 2 : Given a m x n matrix A, find a submatrix of A such that sum of all the elements of the submatrix is the largest amongst all possible submatrices.

Example :

1 2 -1
-3 -1 4
1 -5 -2

Desired sub matrix :

2 -1
-1 4

this idea behind this is : The idea behind the 2D algorithm is that we use brute force on one coordinate(row) and the 1D algorithm on the other.
code refer : http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html

#include<iostream>
using namespace std;

#define M 10
#define N 10

main()
{
int tmp[100], n, x1, x2;
int cur, max_sum, fx1, fx2, fy1, fy2;
int i,j,k;
int input[M][N];
fx1 = fx2 = fy1 = fy2 = max_sum = cur = -1;

for (i=0; i< M; i++)
{
for(k=0; k<N; k++)
tmp[k] = 0;

for (j=i; j<M; j++)
{
for(k=0; k<N; k++)
tmp[k] += input[j][k];

if (cur > max_sum)
{
fy1 = x1;
fy2 = x2;
fx1 = i;
fx2 = j;
max_sum = cur;
}
}
}
cout << "max Sum = " << max_sum << " from (" << fx1 << "," << fy1 << ") to ("
<< fx2 << "," << fy2 << ")" << endl;
}


http://discuss.joelonsoftware.com/default.asp?interview.11.784947.1

not sure the explaining is right or not. http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html