This topic summarizes the contents of our assignment. In this assignment, we presented and discussed the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. The problem of longest common sub sequence arises whenever we search for similarities across multiple texts. A important application is in finding a consensus among DNA sequences.
A string in C is an array of characters. C strings can be numbers, letters or symbols, words or random text, but all strings in this programming language terminate with a null character. Programming in C, you can create strings or manipulate them using various C functions. A substring is a portion of a larger string. There are several mathematical tools for determining if two strings share a common substring.
To qualify as a sub string, the characters of a shorter string must appear in a longer string in order but not necessarily together. Now let’s take an example, "tiger" is a substring of "tiny gherkin" as "t," "i," "g," "e" and "r" all appear in that order in the larger string. If an entire string shows up inside another, larger string, the smaller string is a sub sequence of the big string. With a pair of short strings, picking out a common sub sequence is simple, but as strings grow longer, it's harder to do that with the naked eye.
Let us start with a simple approach, given are two strings: Given two (or three strings), we will find the longest sub string that appears in both two string. the longest common substring problem is to find the longest string (or strings) that is a sub string (or are substrings) of two or more strings. One should not be confused with the longest common subsequence problem. Example the longest common substring of the strings "ABABC", "BABCA" and "ABCBA" is string "ABC" of length 3. Other common substrings are "AB", "BC" and "BA".
Problem definition:
Given two strings say “S” and “T” where S of length m and T of length n, find the longest strings which are substrings of both S and T.
A generalisation is the kcommon substring problem. Given the set of strings S = {S_1, ..., S_K}, where S_i=n_i and Î£n_i = N.
Find for each 2 ≤ k ≤ K, the longest strings which occur as sub strings of at least k strings.
Algorithms:
One can find the starting position and lengths of the longest common substrings of S and T in Theta (n+m)
Pseudo code
The following pseudo code will find the set of longest common substrings between two strings with dynamic programming:
The following method can be used to reduce the memory usage of an implementation:
Keep only the last and current row of the DP table to save memory (O(\min(m, n)) instead of O(n m))
Store only nonzero values in the rows. Hence this can be done using hash tables instead of arrays. This method is useful for large alphabets.
Algorithm for longest common substring matching
Analysis of algorithm :
In this we take the run time of the program logic and values are varied based on the number of character in string1 and string2, then the total number of execution of all logical expressions. we carry this process say upto 20 character.
Suppose, we are taking the
string1 =”a”
string2 =”a”
in the above both substring are equal hence LCS found.
Again we increase characters in string1 and keeping string2 same as two, three etc ,.. character length as N.
We observe that the time complexity increases as the string1 increases.
The count value increases linearly as string length increases. We say that a function has linear complexity as the amount of work is proportional to the size of the input. Complexity = n*m*w.
If both strings are of same length = N,
then O (N^3)
A string in C is an array of characters. C strings can be numbers, letters or symbols, words or random text, but all strings in this programming language terminate with a null character. Programming in C, you can create strings or manipulate them using various C functions. A substring is a portion of a larger string. There are several mathematical tools for determining if two strings share a common substring.
To qualify as a sub string, the characters of a shorter string must appear in a longer string in order but not necessarily together. Now let’s take an example, "tiger" is a substring of "tiny gherkin" as "t," "i," "g," "e" and "r" all appear in that order in the larger string. If an entire string shows up inside another, larger string, the smaller string is a sub sequence of the big string. With a pair of short strings, picking out a common sub sequence is simple, but as strings grow longer, it's harder to do that with the naked eye.
Let us start with a simple approach, given are two strings: Given two (or three strings), we will find the longest sub string that appears in both two string. the longest common substring problem is to find the longest string (or strings) that is a sub string (or are substrings) of two or more strings. One should not be confused with the longest common subsequence problem. Example the longest common substring of the strings "ABABC", "BABCA" and "ABCBA" is string "ABC" of length 3. Other common substrings are "AB", "BC" and "BA".
Problem definition:
Given two strings say “S” and “T” where S of length m and T of length n, find the longest strings which are substrings of both S and T.
A generalisation is the kcommon substring problem. Given the set of strings S = {S_1, ..., S_K}, where S_i=n_i and Î£n_i = N.
Find for each 2 ≤ k ≤ K, the longest strings which occur as sub strings of at least k strings.
Algorithms:
One can find the starting position and lengths of the longest common substrings of S and T in Theta (n+m)
Pseudo code
The following pseudo code will find the set of longest common substrings between two strings with dynamic programming:
This algorithm runs in O(n m) time. The variable z is used to hold the length of the longest common substring found so far. The set ret is used to store the set of strings which are of length z. The set ret can be stored efficiently by just storing the index i, and that is the last character of the longest common substring (of size z) instead of S[iz+1..z]. Thus all the longest common substrings would be, for each i in set ret, S[(ret[i]z).,.(ret[i])].function LCSubstr(S[1..m], T[1..n]) L := array(1..m, 1..n) z := 0 ret := {} or i := 1..m for j := 1..n if S[i] = T[j] if i = 1 or j = 1 L[i,j] := 1 else L[i,j] := L[i1,j1] + 1 if L[i,j] > z z := L[i,j] ret := {} if L[i,j] = z ret := ret ∪ {S[iz+1..i]} else L[i,j]=0; return ret
The following method can be used to reduce the memory usage of an implementation:
Keep only the last and current row of the DP table to save memory (O(\min(m, n)) instead of O(n m))
Store only nonzero values in the rows. Hence this can be done using hash tables instead of arrays. This method is useful for large alphabets.
Algorithm for longest common substring matching
Input : s 1 [ ]<  substring 1 s 2 [ ]<  substring 2 Output : longest common substring l1 = string length (s1); l2 = string length (s2); for i=0 to l1 do for j=0 to l2 do for k=0 to (i+k)<l1 && (j+k)<l2 do //sub function call to check are they equal If (AreEqual(p1, p2, i, j, k)) // if same strings found then count as max if (k>max) lcss = i; max = k; end if end if end for // if max is 0 then there is no common strings if (max==1) display ("No substring found in both string") else display ("Longest common substring length is:" max+1) display ("Longest common substring is:") for i=lcss, j=0 to j<=max do display( p1[i+j]) sub function call: int AreEqual (char *p, char *q, int i, int j, int k) for c=0 to c<=k do if (p[i+c] != q[j+c]) return 0; return 1;
Analysis of algorithm :
In this we take the run time of the program logic and values are varied based on the number of character in string1 and string2, then the total number of execution of all logical expressions. we carry this process say upto 20 character.
Suppose, we are taking the
string1 =”a”
string2 =”a”
in the above both substring are equal hence LCS found.
LCS

Window
Length
(w)

String1
(n)

String2
(m)

Count

1

2

1

40
 
2

4

3

226
 
3

6

5

660
 
4

8

7

1438
 
5

10

9

2656
 
6

12

11

4485
 
7

14

13

6916
 
8

16

15

8994
 
9

18

17

13060
 
10

20

19

18706
 
Again we increase characters in string1 and keeping string2 same as two, three etc ,.. character length as N.
We observe that the time complexity increases as the string1 increases.
The count value increases linearly as string length increases. We say that a function has linear complexity as the amount of work is proportional to the size of the input. Complexity = n*m*w.
If both strings are of same length = N,
then O (N^3)
Time complexity

LCS
 
S/E

Frequency

Total no. of steps

1

1

1

1

1

1

1

L1+1

L1+1

1

L2^2

L2^2

1

(L)^3

(L)^3

1

c

C

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

L^3(7+L1+L2+C)

Here is a implementation of longest common substring matching in C: #include<stdio.h> #include<string.h> #include<conio.h> //sub function to check if two strings are equal or not int AreEqual(char *p, char *q, int i, int j, int k) { int c; for(c=0; c<=k; ++c) if(p[i+c] != q[j+c]) return 0; return 1; } void main() { int l1,l2,temp; int i, j, k, lcss, max=1; char s1[1024], s2[1024]; char *p1, *p2; p1= s1; p2= s2; printf ("\n enter the 1st string "); scanf("%[^\n]", s1); getchar(); printf (" \nenter the 2nd string "); scanf("%[^\n]", s2); l1 = strlen(s1); l2 = strlen(s2); for(i=0; i<l1; ++i) for(j=0; j<l2; ++j) for(k=0; (i+k)<l1 && (j+k)<l2; ++k) { //sub function call to check are they equal ?? if(AreEqual(p1, p2, i, j, k)) { // if same strings found then count as max if (k>max) { lcss = i; max = k; } } } // if max is 0 then there is no common strings :( if (max==1) { printf ("No substring found in both string "); } else { printf("Longest common substring length: %d", max+1); printf("\nLongest common substring is:"); printf("lcs: "); for(i=lcss, j=0; j<=max; ++j) printf("%c", p1[i+j]); printf("\n"); } getch(); }
fantastic analysis which is helped me on the class room to understand better :)
ReplyDelete