ALGORITHM: Pseudo code for `Longest Common Substring & longest consecutive substring`

Longest Common Substring & longest consecutive substring.md

Fun with strings!

Longest Common Substring & longest consecutive substring

The idea here is to get the longest common substring of two or more strings. For example, given the strings Heeeeeeeelllllloooo and teeeeeeeestoooo, it will return the string eeeeeeee, because it is the longest common string of the two.

• See Javascript implementation.

Criteria for deciding if a string is the longest commong substring.

• A character should be repeated multiple times consecutively.
• All the strings should have longest length and should be common among all the strings given to the function.
  • This means that airproof and backroom would have oo as the longest commong substring.

But before we can get the longest commong substring of two or more strings, we should first get their longest consecutive substring, i.e, door has oo as the longest consecutive substring, and the string teeeeeesttt has eeeeee as its longest consecutive substring.

Algorithm to get the longest consecutive substring

The algorithm is composed of 2 loops, one being inside the other. The outer loop acts as the pointer, and the inner loop acts as the checker. The pointer will select a character inside the string, then the checker will check if the next strings that succeeds pointer are the same strings. To maximize the amount of time the algorithm will perform its task, the outer loop would always continue to where the inner loop left of, i.e., if the inner loop ended on string index 9 then the outer loop will continue at string index 9 instead of inner loop + 1.

• Outer loop starts at 0, last loop occurs at string.length - 1
• Inner loop starts at outer loop index, last loop occurs at string.length - 1
• A consecutive substring is only a one-letter that was repeated consecutively, i.e., the string teeeeeesttt would have eeeeee and ttt as its consecutive substring, then the algorithm would choose the longest one which would be eeeeee.

string = 'teeeeeesttt'

1st outer loop
	a = 0
	1st inner loop
		b = a + 1 // 1
		string[a] == string[b]? FALSE
		break out
		// updated longestSubstr = ''
	end inner loop
2nd outer loop
	a = 1
	1st inner loop
		b = a + 1 // 2
		string[a] == string[b]? newLongestSubstr += string[a]
		b == a + 1? newLongestSubstr += string[a]
		// updated newLongestSubstr = ee
	2nd inner loop
		b = b++ // 3
		string[a] == string[b]? newLongestSubstr += string[a]
		b == a + 1? FALSE
		// updated newLongestSubstr = eee
	3rd inner loop
		b = b++ // 4
		string[a] == string[b]? newLongestSubstr += string[a]
		b == a + 1? FALSE
		// updated newLongestSubstr = eeee
	4th inner loop
		b = b++ // 5
		string[a] == string[b]? newLongestSubstr += string[a]
		b == a + 1? FALSE
		// updated newLongestSubstr = eeeee
	5th inner loop
		b = b++ // 6
		string[a] == string[b]? newLongestSubstr += string[a]
		b == a + 1? FALSE
		// updated newLongestSubstr = eeeeee
	6th inner loop
		b = b++ // 7
		string[a] == string[b]? FALSE
		break out
		// updated newLongestSubstr = eeeeee
		// updated longestSubstr = ''
	end inner loop
	newLongestSubstr.length > longestSubstr.length? longestSubstr = newLongestSubstr
	// updated longestSubstr = eeeeee
3rd outer loop
	a = 7
	1st inner loop
		b = a + 1 // 8
		string[a] == string[b]? FALSE
		break out
		// updated longestSubstr = eeeeee
4th outer loop
	a = 8
	1st inner loop
		b = a + 1 // 9
		string[a] == string[b]? newLongestSubstr += string[b]
		b == a + 1? newLongestSubstr += string[b]
		// updated newLongestSubstr = tt
	2nd inner loop
		b = b++ // 10
		string[a] == string[b]? newLongestSubstr += string[b]
		b == a + 1? FALSE
		// newLongestSubstr = ttt
		// updated longestSubstr = eeeeee
	end inner loop
	newLongestSubstr.length > longestSubstr.length? FALSE
end outer loop
// longestSubstr = eeeeee

Algorithm to get the longest common substring

The algorithm would be composed of 2 phases, 3 loops. First phase is to get the longest consecutive substring of every string, that's where you would use the first loop. Then the 2nd and 3rd loop are partners, the 3rd loop being inside the 2nd loop, their main purpose is to compair every lonest consecutive substring with the others and see if they are in common or not common. I want the output to be an array of objects, the object will look something like this:

{
	strings: ['door', 'room'],
	common: 'oo'
}

• outer loop starts at 0, last loop occurs at strings.length - 1
• inner loop starts at outer loop index, last loop occurst at strings.length - 1

With that said, the pseudo code would be as follows:

strings = ['airproof', 'door', 'room']
// phase 1
get the longest consecutive substring for every strings as an array.
loop through the array.
// after phase 1 you'll get
longestConsecutiveSubstrs = ['oo', 'oo', 'oo']
// phase 2
1st outer loop
	a = 0
	1st inner loop
		b = a + 1 // 1
		longestConsecutiveSubstrs[a] == longestConsecutiveSubstrs[b]
			? commonLongestSubstr[] = {
				strings: [string[a], string[b]],
				common: longestConsecutiveSubstrs[b]
			}
			: commonLongestSubstr[] = {
				strings: [string[a], string[b]],
				common: null
			}
		// updated commonLongestSubstr
		// [
		//  {
		//		strings: ['airproof', door'],
		//		common: 'oo'
		// 	}
		// ]
	2nd inner loop
		b = b++ // 2
		longestConsecutiveSubstrs[a] == longestConsecutiveSubstrs[b]
			? commonLongestSubstr[] = {
				strings: [string[a], string[b]],
				common: longestConsecutiveSubstrs[b]
			}
			: commonLongestSubstr[] = {
				strings: [string[a], string[b]],
				common: null
			}
		// updated commonLongestSubstr
		// [
		//  {
		//		strings: ['airproof', door'],
		//		common: 'oo'
		// 	},
		//  {
		//		strings: ['airproof', room'],
		//		common: 'oo'
		// 	}
		// ]
	end inner loop
2nd outer loop
	a = 1
	1st inner loop
		b = a + 1 // 2
		longestConsecutiveSubstrs[a] == longestConsecutiveSubstrs[b]
			? commonLongestSubstr[] = {
				strings: [string[a], string[b]],
				common: longestConsecutiveSubstrs[b]
			}
			: commonLongestSubstr[] = {
				strings: [string[a], string[b]],
				common: null
			}
		// updated commonLongestSubstr
		// [
		//  {
		//		strings: ['airproof', door'],
		//		common: 'oo'
		// 	},
		//  {
		//		strings: ['airproof', room'],
		//		common: 'oo'
		// 	},
		//  {
		//		strings: ['door', 'room'],
		//		common: 'oo'
		// 	}
		// ]