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,
S = “ADOBECODEBANC”
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.

code refer http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html

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];  
            kadane(tmp, N, x1, x2, cur);  

            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

string extra

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License