// Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) // that prints all occurrences of pat[] in txt[]. You may assume that n > m.

NaivePatternSearching.js

// Searching for Patterns | Set 1 (Naive Pattern Searching)

// Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[])
 // that prints all occurrences of pat[] in txt[]. You may assume that n > m.

// Examples:
// 1) Input:

//   txt[] =  "THIS IS A TEST TEXT"
//   pat[] = "TEST"

// Output:

// Pattern found at index 10

// 2) Input:

//   txt[] =  "AABAACAADAABAAABAA"
//   pat[] = "AABA"

// Output:

//    Pattern found at index 0
//    Pattern found at index 9
//    Pattern found at index 13

// Pattern searching is an important problem in computer science.
// When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results.

/// Analysis
//// O(N*m) where N is size of string and m is size of pattern 
///// start at index = 0 (idx_i) to N and create a sub-loop from 0 to m (idx_j)
///// if str[idx_j] == pat[idx_j] continue , else break and increment idx_i 
////// if any of idx_j == m then the pattern is fully satisfied and note the idx_i in match array
///// return the match array


function solution(str,ptn) {
	var match = [];
	var k=0;
	for(var i=0;i<str.length;i++) {
		var i_is_match=false;
		for(var j=0;j<ptn.length;j++) {
			if(str[parseInt(i+j)] == ptn[j]) {
				i_is_match = true;
				// console.log(str[parseInt(i+j)] + " == " + ptn[j] + " for j ="+j + " and i+j="+parseInt(i+j));
			}
			else {
				i_is_match = false;
				// console.log(str[i+j] + " == " + ptn[j] + " for j ="+j + " and i+j="+parseInt(i+j));
				break;
			}
		}
		// console.log("i_is_match == "+ i_is_match);
		if(i_is_match == true) {
			// console.log("adding i to match i="+i);
			match[k++] = i;
			i_is_match = false;
		}
	}
	return match;
}



console.log(solution("THIS IS A TEST TEXT","TEST"));
console.log(solution("AABAACAADAABAAABAA","AABA"));
console.log(solution("AABCCAADDEE","FAA"));
console.log(solution("AAAAAAAAAAAAAAAAAA","AAAAA"));
console.log(solution("AAAAAAAAAAAAAAAAAB",""))


////// Notes /////

// Slide the pattern over text one by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches. 
// Number of comparisons in worst case is O(m*(n-m+1)). 
// Although strings which have repeated characters are not likely to appear in English text, they may well occur in other applications (for example, in binary texts). 
// The KMP matching algorithm improves the worst case to O(n).