Given n arbitrary strings S1, S2,…,Sn, maximize the function
f(Si, Si+1, …, Sj) = length(Si) + length(Si+1)+ … + length(Sj)
under the given constraints c(Sp,…,Sq), which means strings Sp,…,Sq cannot be taken together.
Program
#include #define NANSWERS 3 // max no of strings in the answer. #define MAXCONS 5 // max length of any constraint. typedef enum {FALSE, TRUE} bool; bool isAbsent(int strnum, int *answer, int nans) { /* * returns TRUE if answer[nans] does NOT contain strnum. */ int i; for(i=0; i−1. */ int i, j; for(i=0; i−1; ++j) if(isAbsent(constraints[i][j], answer, nans)) break; if(constraints[i][j] == −1) return FALSE; } return TRUE; } void findMaxComb(int *lengths, int nstr, int constraints[][MAXCONS+1], int ncons, int *answer, int nans, int *maxsum, int startstr, int startans, int currsum ) { /* * find the max sum of lengths of nans strings out of nstr strings of * lengths lengths[] satisfying ncons constraints constraints[]. * save the max sum in *maxsum and the string indices in answer[]. */ int i; if(startans < nans) { for(i=startstr; i *maxsum) { if(satisfies(answer, nans, constraints, ncons)) *maxsum = currsum; } } int main() { int lengths[] = {9, 8, 6, 5, 4, 3}; // lengths[i] = length(string[i]). int answer[NANSWERS]; // indices of strings. int constraints[][MAXCONS+1] = { // index of string starts with 1 so that {1,3,−1}, // end of constraint can be signified {2,−1}, // by 0. {1,5,−1}, // we decrement every index so that {3,4,−1}, // each constraint ends with −1. {0,4,5,−1}, {0,4,−1}, {0,3,5,−1} }; int ncons = sizeof(constraints)/sizeof(int)/(MAXCONS+1); // no of constraints. int nstr = sizeof(lengths)/sizeof(int); // no of strings. int i, j; int maxsum = 0; for(i=1; i<=NANSWERS; ++i) { findMaxComb(lengths, nstr, constraints, ncons, answer, i, &maxsum, 0, 0, 0); printf("After %d strings: maxsum=%d. ", i, maxsum); //maxsum = 0; // this will keep all length combinations separate. } return 0; }
Explanation
I 
string combination 
currsum 
maxsum 
currsum > maxsum 
satisfiesallconstraints? 
maxsum 

1 
0 
9 
0 
yes 
yes 
9 
1 to 5 
<9 
9 
no 
— 
9 

2 
0, 1 
17 
9 
yes 
yes 
17 
other combinations 
<17 
17 
no 
— 
17 

3 
0, 1, 2 
23 
17 
yes 
no 
17 
0, 1, 3 
22 
17 
yes 
no 
17 

0, 1, 4 
21 
17 
yes 
no 
17 

0, 1, 5 
20 
17 
yes 
no 
17 

0, 2, 3 
20 
17 
yes 
no 
17 

0, 2, 4 
19 
17 
yes 
no 
17 

0, 2, 5 
18 
17 
yes 
no 
17 

0, 3, 4 
18 
17 
yes 
no 
17 

0, 3, 5 
17 
17 
no 
— 
17 

0, 4, 5 
16 
17 
no 
— 
17 

1, 2, 3 
19 
17 
yes 
no 
17 

1, 2, 4 
18 
17 
yes 
no 
17 

1, 2, 5 
17 
17 
no 
— 
17 

2, 3, 4 
15 
17 
no 
— 
17 

other combinations 
<17 
17 
no 
— 
17 
Points to Remember
Given n arbitrary strings S1, S2, …, Sn, maximize the function
f(Si, Si+1, …, Sj) = length(Si) + length(Si+1)+ … + length(Sj)
under the given constraints c(Si, Sj) which means Si and Sj cannot be taken together.
Program
#include #define MININT 1000 #define MAXVERTICES 10 #define MAXPATHVERT 3 void printCosts( int a[][MAXVERTICES], int nvert, int pathvert[][MAXVERTICES] ) { /* * prints min cost matrix a. */ int i, j; for( i=0; i a[i][j]; * and h1+h2−1 < MAXPATHVERT; * return the sum. */ int p, q; int maxsum = 0; *h1 = *h2 = −1; for(p=2; p−1 <= MAXPATHVERT && b[p][i][k]>0 && b[q][k][j]>0 && b[p][i][k]+b[q][k][j] > maxsum) maxsum=b[p][i][k]+b[q][k][j], *h1=p, *h2=q; } if(maxsum > a[i][j]) return maxsum; *h1 = *h2 = −1; return −1; } void allCosts(int cost[][MAXVERTICES], int a[][MAXVERTICES], int nvert){ int i, j, k; int pathvert[MAXVERTICES][MAXVERTICES] ; int b[MAXPATHVERT+1][MAXVERTICES][MAXVERTICES] ; int sum, h1, h2; int l; for( i=0; i−1 && h1 != −1 && a[i][j]>=0) { //printf("a[i][j]=%d, h1=%d, h2=%d. ", sum, h1, h2); a[i][j] = sum, b[h1+h2−1][i][j] = sum, pathvert[i][j]=h1+h2−1; } } printCosts(a, nvert, pathvert); } } int main() { int cost[MAXVERTICES][MAXVERTICES] = { {0,50,10,MININT,45,MININT}, {MININT,0,15,MININT,10,MININT}, {20,MININT,0,15,MININT,MININT}, {MININT,20,MININT,0,35,MININT}, {MININT,MININT,MININT,30,0,MININT}, {MININT,MININT,MININT,3,MININT,0} }; /* {20,30,40,50}, {MININT,40,50,60}, {MININT,MININT,60,70}, {MININT,MININT,MININT,80} , {2,3,4,5}, {3,4,5,6}, {4,5,6,MININT}, {5,6,MININT,8} , {0,1,2,MININT}, {3,0,MININT,4}, {MININT,MININT,0,6}, {MININT,5,MININT,0} }; */ int a[MAXVERTICES][MAXVERTICES] ; int nvert = 6; // no of vertices. /*print( cost, nvert ); */ allCosts( cost, a, nvert ); //printCosts( a, nvert ); return 0; }
Explanation
We define a similar problem of finding the longest path between any pair of vertices in the graph, called the longest path problem. If we allow inclusion of a vertex more than once, there is a possibility of getting into an infinite loop and the procedure may not terminate! So we put a limit on the number of vertices that can be included in the longest path.
Points to Remember
Write a program to find closure of a set of characters input as a string.
Program
#include #define MAXLEN 80 void init(char *answer, int slen) { /* * initialize first slen entries in answer[] to 0. */ int i; for(i=0; i−1; i>=0; i) { // i represents the bit pattern. // 1 in the bit pattern means char should be displayed. fillBitwise(i, str, s, slen); init(answer, strlen(str)); printf("printComb(%s). ", str); printComb(str, strlen(str), answer); getchar(); } } int main() { char s[MAXLEN]; printf("Enter characters for closure: "); gets(s); while(*s) { //init(answer, strlen(s)); //printComb(s, strlen(s), answer); findClosure(s, strlen(s)); printf("Enter characters for closure(press enter to end): "); gets(s); } return 0; }
Explanation
Thus, closure(abc) = comb(abc) 
/* strings of length 3. */ 
+ comb(ab) + comb(bc) + comb(ac) 
/* strings of length 2. */ 
+ comb(a) + comb(b) + comb(c) 
/* strings of length 1. */ 
+ comb(‘’) 
/* empty string. */ 
abc 
ó 
111 
ab 
ó 
110 
ac 
ó 
101 
a 
ó 
100 
bc 
ó 
011 
b 
ó 
010 
c 
ó 
001 
‘’ 
ó 
000 
Thus, we generate bit patterns as shown to represent different strings and then call comb() with these input parameters. Note further that these bit patterns are nothing but numbers 0 to 2^n−1.
Points to Remember
Write a program to find the edit distance between two character strings.
Program
#include #define MAXLEN 80 int findMin(int d1, int d2, int d3) { /* * return min of d1, d2 and d3. */ if(d1 < d2 && d1 < d3) return d1; else if(d1 < d3) return d2; else if(d2 < d3) return d2; else return d3; } int findEditDistance(char *s1, char *s2) { /* * returns edit distance between s1 and s2. */ int d1, d2, d3; if(*s1 == 0) return strlen(s2); if(*s2 == 0) return strlen(s1); if(*s1 == *s2) d1 = findEditDistance(s1+1, s2+1); else d1 = 1 + findEditDistance(s1+1, s2+1); // update. d2 = 1+findEditDistance(s1, s2+1); // insert. d3 = 1+findEditDistance(s1+1, s2); // delete. return findMin(d1, d2, d3); } int main() { char s1[MAXLEN], s2[MAXLEN]; printf("Enter string 1: "); gets(s1); while(*s1) { printf("Enter string 2: "); gets(s2); printf("Edit distance(%s, %s) = %d. ", s1, s2, findEditDistance(s1, s2)); printf("Enter string 1(enter to end): "); gets(s1); } return 0; }
Explanation
T(n) = 3*T(n−1)
where n is the minimum of the two lengths of the strings. Solving this recurrence relation gives us the complexity O(3^n).
Points to Remember
Find the maximum matching pattern in an input string. Note that the matching pattern may be separated by some other patterns.
Program
#include #define MAXLEN 80 void findMaxPat(char *s, char *pat, int *maxpat) { int i; for(i=0; *s && *pat; ++s, ++i) if(*s == *pat) *maxpat++=i, pat++; if(!*pat) printf("whole pat found. "); else printf("whole pat NOT found. "); *maxpat = −1; // end of maxpat. } void printMaxPat(char *s, int *maxpat) { char *sptr = s; puts(s); for(; *sptr && *maxpat != −1; ++sptr) { if(sptrs == *maxpat) { printf("^"); maxpat++; } else printf("%c", ' '); } printf(" "); } int main() { char s[MAXLEN]; char pat[MAXLEN]; int maxpat[MAXLEN]; printf("Enter main string: "); gets(s); while(*s) { printf("Enter pattern to be searched: "); gets(pat); findMaxPat(s, pat, maxpat); printMaxPat(s, maxpat); printf("Enter main string: "); gets(s); } return 0; }
Explanation
h e l l o w o r l d ^ ^ ^ ^.
Points to Remember
Write a function to compare two strings using the soundex method.
Program
#include #define MAXLEN 80 #define NALPHA 26 char *soundexGroups[] = { "aeiouhyw", "kcgjqsxz", "td", "bpfv", "l", "mn", "r" }; int soundexCodes[NALPHA]; void soundexInit() { /* * build an inverted index from the global table soundexGroups[]. * the inverted index is stored in global soundexCodes[]. */ int i; char *sptr; for(i=sizeof(soundexGroups)/sizeof(char *)−1; i>=0; i) for(sptr=soundexGroups[i]; *sptr; ++sptr) soundexCodes[*sptr'a'] = i; } int compareCodes(int *soundex1, int *soundex2) { int *ptr1, *ptr2; for(ptr1=soundex1, ptr2=soundex2; *ptr1!=−1 && *ptr2!=−1 && *ptr1==*ptr2; ++ ptr1, ++ptr2) ; return *ptr1 == *ptr2; } void findSoundex(char *s, int *soundex, char lastchar) { /* * find the soundex code for s and save in soundex. * the stored value is the index in the array of soundex codes. * function is recursive. * start by changing multiple occurrences of chars in consecutive positions * by single occurrences. * end soundex by −1. * lastchar == −1 implies this is the first call to this function. */ if(!*s) *soundex = −1, lastchar = 0; else if(*s == lastchar) findSoundex(s+1, soundex, lastchar); else if(lastchar == −1) // *s is the first char. *soundex=soundexCodes[*s'a'], findSoundex(s+1, soundex+1, *s); else if(soundexCodes[*s'a'] == 0) // vowel group. findSoundex(s+1, soundex, *s); else *soundex=soundexCodes[*s'a'], findSoundex(s+1, soundex+1, *s); } int compareSoundex(char *s1, char *s2) { /* * find soundex codes for s1 and s2. * return 1 if codes are equal else 0. */ int soundex1[MAXLEN], soundex2[MAXLEN]; findSoundex(s1, soundex1, −1); findSoundex(s2, soundex2, −1); return compareCodes(soundex1, soundex2); } int main() { char s1[MAXLEN]; char s2[MAXLEN]; soundexInit(); printf("Enter string 1: "); gets(s1); while(*s1) { printf("Enter string 2: "); gets(s2); printf("(%s == %s) = %d. ", s1, s2, compareSoundex(s1, s2)); printf("Enter string 1(enter to end): "); gets(s1); } return 0; }
Explanation
Group Number 
Characters 

0 
aeiouhwy 
1 
bpfv 
2 
cgjkqsxz 
3 
dt 
4 
l 
5 
mn 
6 
r 
Thus, the soundex code for the word ‘cross’ is ‘26022’. By soundex, the words ‘think’ and ‘thing’ will be the same as they both have the same soundex code, ‘30052’. Note that they both sound similar.
Thus, the new soundex code for ‘cross’ is ‘262’ and the one for ‘alpha’ is ‘041’.
Points to Remember
Part I  C Language
Part II  Data Structures
Part III  Advanced Problems in Data Structures