Monthly Archives: December 2013

Prefix to infix Conversion – Using Lex

0
Posted on by

Algorithm : 

  Scan tokens from left to right

  if you find a operator push it into stack

 if you find a operand print it and also pop the operator from the top of the stock and print it

%{
char stack[100];
int tos=0;
void push(char ch);
%}
%%
[a-zA-Z] { printf("%c %c ",yytext[0],stack[--tos]); }
[+\*\/\(\)\-] { push(yytext[0]); }
%%
void push(char ch){
stack[tos++]=ch;
}
int yywrap(){
return 1;
}
int main()
{
yylex();
return 0;
}
view raw prefixtoinfix.l hosted with ❤ by GitHub

Spoj(EDIST) – Edit Distance -Dynamic Programming

0
Posted on by

 

2013-12-13 19.26.29

http://www.spoj.com/problems/EDIST/

Consider the string SAT .We need to convert it into SAIT

there are 3 possibilities as seen in the picture

So the recursive rule goes like this

dp[i,j]=edit distance for strings of length i and j

dp[i,j]= min(dp[i-1,j-1]+(X[i-1]!=Y[j-1]),dp[i-1,j]+1,dp[i,j-1]+1)

Here X and Y are strings with 0 based index i.e  X[i-1] denotes ith character in X

With the base conditions

dp[0,j]=j //just insertions

dp[j,0]=j //just deletions

#include<iostream>
#include<string.h>
using namespace std;
char str1[2001];
char str2[2001];
int dp[2001][2001];
int main(){
int t;
cin>>t;
while(t--){
cin>>str1>>str2;
int d1,d2,d3,i,j,len1,len2;
len1=strlen(str1);
len2=strlen(str2);
for( i=0;i<=len1;i++)
dp[i][0]=i;
for( j=1;j<=len2;j++)
dp[0][j]=j;
for( i=1;i<=len1;i++){
for( j=1;j<=len2;j++){
d1=((str1[i-1]==str2[j-1])?0:1)+dp[i-1][j-1];//substitution-->if last character same dont do anything(0) else replace last char(1
d2=dp[i][j-1]+1; // convert (s+ch1) to (t+ch2) by inserting in ch2. so dp (s+ch1,t)+1 +1 for ch2 insertion
//insertion-->str2 of j-1 length is converted to
d3=dp[i-1][j]+1;//deletion -->convert (s+ch1) to (t+ch2) by deleting ch1 from s.so dp[s,t+ch2]+1 +1 for ch1 deletion
//finding minimum of 3
if(d1<d2&&d1<d3)
dp[i][j]=d1;
else{
if(d2<d3)
dp[i][j]=d2;
else
dp[i][j]=d3;
}
}
}
cout<< dp[len1][len2];
cout<<endl;
}
}
view raw EDIST.cpp hosted with ❤ by GitHub

Spoj (SUBS) – String it out

0
Posted on by

http://www.spoj.com/problems/SUBS/

There is  a very interesting algorithmic approach for this problem

(Thanks to topcoder forum from where i got this idea)

To find the maximum power using which X can be expanded such that X is a subsequence in Y

highest possible power = length_of_Y/length_of_X

lowest power= 0

Now using binary search find the maximum valid power whose value is in the range [0,highest possible power]

[gist https://gist.github.com/vishnujayvel/7907760 ]

Spoj (DSUBSEQ) – Distinct Subsequences

0
Posted on by

http://www.spoj.com/problems/DSUBSEQ/

Consider the string “ABCD”

Let dp[i] = { number of subsequences possible from string[1…i]}

Note : we are considering 1 based string array

what are all the possible subsequences

dp[0] = 1   { }

dp[1]= 2   { } ,A

dp[2] = 4  { } ,A ,B ,AB

dp[3] = 8  { } ,A ,B ,AB ,C ,AC,BC,ABC

dp[4] = 16 { } ,A ,B ,AB ,C ,AC,BC,ABC,D,AD,BD,ABD,CD,ACD,BCD ,ABCD

So do we get some kind of pattern ?

yes!

dp[i]= dp[i-1]*2

(sum of all subseq till string[1…i-1] + sum of subseq till string[1…i-1] concatenated with character string[i])

There one more case we have to consider

if we have duplicate characters in the string then our subsequence will also be duplicated

To prevent that have a last[ ] array to store position of string[i] which occured before

last[string[i]]= last occurence of string[i]

substract subsequence count occured till position (last[string[i]]-1) since it is repeated again

so the correct recursion rule is

dp[i]=dp[i-1]*2;

if(last[string[i]]>0)

dp[i]=(dp[i]-dp[last[string[i]]-1]);