LongestCommonExtension-naive.js

// Longest Common Extension / LCE | Set 1 (Introduction and Naive Method)

// The Longest Common Extension (LCE) problem considers a string s and computes, for each pair (L , R), the longest sub string 
// of s that starts at both L and R. In LCE, in each of the query we have to answer the length of the longest common prefix 
// starting at indexes L and R.


// example
// String : “abbababba”
// Queries: LCE(1, 2), LCE(1, 6) and LCE(0, 5)

// Find the length of the Longest Common Prefix starting at index given as, (1, 2), (1, 6) and (0, 5).
// ans : LCE(1,2) = 1 , LCE(1,6)=3 , LCE(0,5)=4

/////Analysis
/// to find LCE(x,y) you start at the location given and start checking the char at the indexes,
/// if the chars are the same then add 1 to both indexes and continue , if they are not the same then break and give
/// the output of the count as LCE. keep doing this until there is a mismatch or until x = y


function solution(str,idx1,idx2) {
	var idx2start = idx2;
	var len=0;
	while(idx1 < idx2start && str[idx1] == str[idx2]) {
		len++;
		idx1++;
		idx2++;
	}
	return len;
}

console.log(solution("abbababba",1,2));
console.log(solution("abbababba",1,6));
console.log(solution("abbababba",0,5));

// Notes:
// Analysis of Naive Method

// Time Complexity: The time complexity is O(Q.N), where
// Q = Number of LCE Queries
// N = Length of the input string

// One may be surprised that the although having a greater asymptotic time complexity, the naive method outperforms other efficient method(asymptotically) in practical uses. We will be discussing this in coming sets on this topic.

// Auxiliary Space: O(1), in-place algorithm.

// Applications:

//     K-Mismatch Problem->Landau-Vishkin uses LCE as a subroutine to solve k-mismatch problem
//     Approximate String Searching.
//     Palindrome Matching with Wildcards.
//     K-Difference Global Alignment.

// In the next sets we will discuss how LCE (Longest Common Extension) problem can be reduced to a RMQ (Range Minimum Query). We will also discuss more efficient methods to find the longest common extension.

// Reference :
// http://www.sciencedirect.com/science/article/pii/S1570866710000377