Admin at 06:59, 29 May 2017

2017-05-29T06:59:45Z

← Older revision		Revision as of 06:59, 29 May 2017
Line 37:		Line 37:


	{{~~CSFlag~~}}		{{AlgorithmComplexityFlag}}
	~~[[Category:Algorithms]]~~

	[[Category:Java]]		[[Category:Java]]
	[[Category:C]]		[[Category:C]]

Admin at 08:12, 28 May 2017

2017-05-28T08:12:35Z

← Older revision		Revision as of 08:12, 28 May 2017
Line 37:		Line 37:


			{{CSFlag}}
			[[Category:Algorithms]]

	~~[[Category:Algorithms]]~~
	~~[[Category:CS]]~~
	[[Category:Java]]		[[Category:Java]]
	[[Category:C]]		[[Category:C]]

Admin: Created page with "Consider the following substring matching program:

 int findmatch(char *p, char *t) {  	int i,j; 	int m,n;  	m = strlen(p); 	n = strlen(t);  	for(i=0; i<=(n-m); i=i+1) {..."

2017-05-28T08:11:03Z

Created page with "Consider the following substring matching program: <pre> int findmatch(char *p, char *t) { int i,j; int m,n; m = strlen(p); n = strlen(t); for(i=0; i<=(n-m); i=i+1) {..."

New page

Consider the following substring matching program:

<pre>
int findmatch(char *p, char *t) {
int i,j;
int m,n;

m = strlen(p);
n = strlen(t);

for(i=0; i<=(n-m); i=i+1) {
j=0;
while((j<m)&&(t[i+j]==p[j]))
j = j+1;
if(j==m)
return(i);
}
}
</pre>

The worst case running time of the two nested for loops can be analyzed as follows.

The two strlen() calls are O(n) and O(m), respectively.

The for loop runs a maximum of (n-m) times.

The inner for loop runs a maximum of m times.

This the overall algorithm <math>O(n) + O(m) + O((n-m)(m))</math>

The leading terms go away, and the last term becomes:

<math>O((n-m)(m)) \sim O(nm) - O(m^2)</math>

Because we know that n is much greater than m, and because of the leading minus term, the O(m^2) term goes away as well. The final analysis is that the algorithm cost is <math>O(nm)</math>.

[[Category:Algorithms]]
[[Category:CS]]
[[Category:Java]]
[[Category:C]]

Algorithmic Analysis of Substring Pattern Matching - Revision history

Admin at 06:59, 29 May 2017

Admin at 08:12, 28 May 2017

Admin: Created page with "Consider the following substring matching program:
int findmatch(char p, char t) { int i,j; int m,n; m = strlen(p); n = strlen(t); for(i=0; i<=(n-m); i=i+1) {..."