Edit Distance

Edit Distance

One of the classic problems solvable by dynamic programming is computing the “edit distance” between two strings: the minimum number of single-character insertions, deletions, or replacements required to convert one string into another.

For example, the edit distance between “Hello” and “Jello” is 1. The edit distance between “good” and “goodbye” is 3. The edit distance between any string and itself is 0.

The edit distance can be used for such purposes as suggesting, in a spell checker, a list of plausible replacements for a misspelled word. For each word not found in the dictionary (and therefore presumably misspelled), list all words in the dictionary that are a small edit distance way from the misspelling.

Server and client example with C sockets on Linux

In this example we shall build a basic ECHO client and server. The server/client shown here use TCP sockets or SOCK_STREAM. TCP sockets are connection oriented, means that they have a concept of independant connection on a certain port which one application can use at a time. The concept of connection makes TCP a "reliable" stream such that if errors occur, they can be detected and compensated for by resending the failed packets.

Server

Lets build a very simple web server. The steps to make a webserver are as follows :

1. Create socket
2. Bind to address and port
3. Put in listening mode
4. Accept connections and process there after.

UVA 326

http://uva.onlinejudge.org/external/3/326.html

using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<cmath>
#include<queue>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
int main()
{
    int N,t,k;
    while(cin>>N && N)
    {
        vector<int> inp;
        FOR(i,N)
        {
            cin>>t;
            inp.push_back(t);
        }
        cin>>k;
        vector<int> res;
        res.push_back(inp[inp.size()-1]);
        for(int i=0;i<N-1;i++)
        {
            for(int j=N-1;j>i;j–)
            {
                inp[j]=inp[j]-inp[j-1];
            }
            res.push_back(inp[N-1]);
        }
        for(int j=0;j<k;j++)
        {
            for(int i=res.size()-2;i>=0;i–)
            {
                res[i]=res[i]+res[i+1];
            }
        }
        printf(“Term %d of the sequence is %d\n”,N+k,res[0]);
    }
}

UVA 507

http://uva.onlinejudge.org/external/5/507.html

#include<iostream>
using namespace std;

void max(int a[],int n,int j)
{
 int m_s=1,m_e=2,m=a[0],s=a[0],st=0;
 
 for (int i=1;i<n;i++)
 {
  if (s>=0)
   s+=a[i];
  else
  {
   st=i;
   s=a[i];
  }
  
  if (s>m)
  {
   m=s;
   m_s=st+1;
   m_e=i+2;
  }
  else if (s==m)
  {
   if (i-st > m_e-m_s)
   {
    m=s;
    m_s=st+1;
    m_e=i+2;
   }
   else if (i-st == m_e-m_s)
   { 
    if (st < m_s)
    {
     m=s;
     m_s=st+1;
     m_e=i+2;
    }
   }
  }
 }
 
 if (m>=0)
  cout<<"The nicest part of route "<<j<<" is between stops "<<m_s<<" and "<<m_e<<endl;
 else
  cout<<"Route "<<j<<" has no nice parts\n";
}

int main()
{
 int n,s;
 cin>>n;
 for (int i=1;i<=n;i++)
 {
  cin>>s;
  int a[s-1];
  for (int j=0;j<s-1;j++)
   cin>>a[j];
  
  max(a,s-1,i);
 }
}

UVA 481

http://uva.onlinejudge.org/external/4/481.html

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
 vector<int> p(a.size());
 int u, v;
 
 if (a.empty()) return;
 
 b.push_back(0);
 
 for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
  if (a[b.back()] < a[i]) 
                {
   p[i] = b.back();
   b.push_back(i);
   continue;
  }
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
  for (u = 0, v = b.size()-1; u < v;) 
                {
   int c = (u + v) / 2;
   if (a[b[c]] < a[i]) u=c+1; else v=c;
  }
 
                // Update b if new value is smaller then previously referenced value 
  if (a[i] < a[b[u]]) 
                {
   if (u > 0) p[i] = b[u-1];
   b[u] = i;
  } 
 }
 
 for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
 int a[100000],i=0;
 
 while(scanf("%d",&a[i])!=EOF)
  i++;
 vector<int> seq(a, a+i); // seq : Input Vector
 vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
        printf("%d\n-\n",lis.size());
 for (size_t i = 0; i < lis.size(); i++)
  printf("%d\n", seq[lis[i]]);   
 
 return 0;
}

UVA 616

http://uva.onlinejudge.org/external/6/616.html

#include<iostream>
using namespace std;

int no(int c);
void print(int p,int n);

int main()
{
 int c,p;

 cin>>c;
 while(c>0)
 {
  p=no(c);
  print(p,c);
  cin>>c;
 }
}

void print(int p,int n)
{
 if(p>0)
 {
  cout<<n<<" coconuts, "<<p<<" people and 1 monkey\n";
 }
 else
  cout<<n<<" coconuts, no solution\n";
}


int no(int c)
{
 int j,a,b,d;

 for(int i=10;i>1;i--)
 {
  if(c%i==1)
  {
   b=c;
   a=1;
   for(j=1;j<=i;j++)
   {
    if (b%i==1)
    {
     b=((b-1)/i)*(i-1);
    }
    else
    {
     a=0;
     break;
    }
   }
   if ((a==1)&&(b%i==0))
   {
    return i;
   }
   else if ((a==0)&&(i==2))
    return -1;
  }
 }
 return -1;
}

CYK algorithm implementation

Implementation of CYK algorithm in C++

The CYK algorithm is a parsing algorithm for context-free grammars. It employs bottom-up parsing and dynamic programming. It is used to check whether a particular string can be generated from a set of productions or not.

#include<iostream>  
#include<cstring>
#include<algorithm>
#include<string>
#include<cassert>
#include<iomanip>
using namespace std;

#define MAX 100
#define for(i,a,b) for(i=a;i<b; i++)

string gram[MAX][MAX];	//to store entered grammar
string dpr[MAX];
int p,np;		//np-> number of productions

inline string concat( string a, string b)	//concatenates unique non-terminals
{
	int i;
	string r=a;
	for(i,0,b.length())
		if(r.find(b[i]) > r.length())
			r+=b[i];
	return (r);
}

inline void break_gram(string a)	//seperates right hand side of entered grammar
{
	int i;
	p=0;
	while(a.length())
	{
		i=a.find("|");
		if(i>a.length())
		{
			dpr[p++] = a;
			a="";
		}
		else
		{
			dpr[p++] = a.substr(0,i);
			a=a.substr(i+1,a.length());
		}
	}
}

inline int lchomsky(string a)	//checks if LHS of entered grammar is in CNF
{
	if(a.length()==1 && a[0]>='A' && a[0]<='Z')
		return 1;
	return 0;
}

inline int rchomsky(string a)	//checks if RHS of grammar is in CNF
{
	if (a.length() == 1 && a[0]>='a' && a[0] <='z')
		return 1;
	if (a.length()==2 && a[0]>='A' && a[0]<='Z' && a[1]>='A' && a[1]<='Z' )
		return 1;
	return 0;
}

inline string search_prod(string p)	//returns a concatenated string of variables which can produce string p
{
	int j,k;
	string r="";
	for(j,0,np)
	{
		k=1;
		while(gram[j][k] != "")
		{
			if(gram[j][k] == p)
			{
				r=concat(r,gram[j][0]);
			}
			k++;
		}
	}	
	return r;
}

inline string gen_comb(string a, string b)	//creates every combination of variables from a and b . For eg: BA * AB = {BA, BB, AA, BB}
{
	int i,j;
	string pri=a,re="";
	for(i,0,a.length())
		for(j,0,b.length())
		{
			pri="";
			pri=pri+a[i]+b[j];
			re=re+search_prod(pri);		//searches if the generated productions can be created or not
		}		
	return re;
}

int main()
{
	int i,pt,j,l,k;
	string a,str,r,pr,start;
	cout<<"\nEnter the start Variable ";
	cin >> start;
	cout<<"\nNumber of productions ";
	cin >> np;
	for(i,0,np)
	{
		cin >> a;
		pt=a.find("->");
		gram[i][0] = a.substr(0,pt);
		if (lchomsky(gram[i][0]) == 0)
		{
			cout<<"\nGrammar not in Chomsky Form";
			abort();
		}
		a = a.substr(pt+2, a.length());
		break_gram(a);
		for(j,0,p)
		{
			gram[i][j+1]=dpr[j];
			if (rchomsky(dpr[j]) == 0)
			{
				cout<<"\nGrammar not in Chomsky Form";
				abort();
			}
		}
	}
	string matrix[MAX][MAX],st;
	cout<<"\nEnter string to be checked : ";
	cin >> str;
	for(i,0,str.length())		//Assigns values to principal diagonal of matrix
	{
		r="";
		st = "";
		st+=str[i];
		for(j,0,np)
		{
			k=1;
			while(gram[j][k] != "")
			{
				if(gram[j][k] == st)
				{
					r=concat(r,gram[j][0]);
				}
				k++;
			}
		}
		matrix[i][i]=r;
	}
	int ii,kk;
	for(k,1,str.length())		//Assigns values to upper half of the matrix
	{
		for(j,k,str.length())
		{
			r="";
			for(l,j-k,j)
			{
				pr = gen_comb(matrix[j-k][l],matrix[l+1][j]);
				r = concat(r,pr);
			}
			matrix[j-k][j] = r;
		}
	}

	for(i,0,str.length())	//Prints the matrix
	{
		k=0;
		l=str.length()-i-1;
		for(j,l,str.length())
		{
			cout<<setw(5)<<matrix[k++][j]<<" ";
		}
		cout<<endl;
	}
			
	int f=0;
	for(i,0,start.length())
		if(matrix[0][str.length()-1].find(start[i]) <= matrix[0][str.length()-1].length())	//Checks if last element of first row contains a Start variable
		{
			cout<<"String can be generated\n";
			return 0;
		}
	cout<<"String cannot be generated\n";
	return 0;
}

Sample Input ::

Enter the start Variable S

Number of productions 4

S->AB|BC
A->BA|a
B->CC|b
C->AB|a

Enter string to be checked :baaba

Output ::