Check if string contains substring without using any standard JavaScript methods?

Question

So I need to implement a javascript method which will return true or false depending on if the masterString contains a subString.

I did something like following but not sure if this is the right approach :

function contains(masterString, subString) {
if(subString.length > masterString.length){
 return false;
}
for(var i=subString.length-1; i<masterString.length; i++){
 if(concatString(i - subString.length-1, i, masterString) === subString){
 return true;
 }
}
 return false;
}
function concatString(index1, index2, string){
 var conString = '';
 console.log(index1, index2-1, string);
 for(var i=index1; i<index2-1; i++){
 conString += string[i];
 }
 console.log(conString);
 return conString;
}
contains('abcd', 'bc');

It isn't working fine though.

Can we implement it? Thanks :)

• Jeremy J Starcher: "...without using any standard JavaScript methods?" Why such a restriction?
• RainingChain: Most likely it's a homework...
• RomanPerekhrest: I see no benefits of such approach: bad readability, bad flexibility, a lot of code ... perhaps, only testing for loop(just for fun)
• Vaibhav Pachauri: yeah.. a homework you can say :)

Answer 1

For each possible index, test if subString is on that index of masterString.

var indexOf = function(masterString,subString){
 for(var i = 0 ; i < masterString.length - subString.length + 1; i++){
 var match = true;
 for(var j = 0; j < subString.length; j++){
 if(masterString[i + j] !== subString[j]){
 match = false;
 break;
 }
 }
 if(match)
 return i;
 } 
 return -1;
} 
var contains = function(master,sub){ 
 return indexOf(master,sub) !== -1; 
}

Note: There are faster algorithms to achieve that like Knuth–Morris–Pratt.

Answer 2

You have a good solution. But I think mine is easier.

By the way: I think .length is a javascript funciton too.

function length(string){
 var count = 0;
 while(string[count] != undefined)
 count++;
 return count;
}
function contains(masterString, subString) {
 var masterStringLength = length(masterString);
 var subStringLength = length(subString);
 for(var i = 0; i <= masterStringLength - subStringLength; i++)
 {
 var count = 0;
 for(var k = 0; k < subStringLength; k++)
 {
 if(masterString[i + k] == subString[k])
 count++;
 else
 break;
 }
 if(count == subStringLength)
 return true;
 }
 return false;
}
console.log(contains('abcdefgh', 'bcde'));
console.log(contains('abcdefgh', 'ab'));
console.log(contains('abcdefgh', 'fgh'));

• Oriol: length is not a function. Not even a getter. Just a data property. See spec

Answer 3

You can use a nested loop:

function contains(masterString, subString) {
 outerloop:
 for(var i=0; i <= masterString.length-subString.length; ++i) {
 for(var j=0; j<subString.length; ++j)
 if(masterString[i + j] !== subString[j]) continue outerloop;
 return true;
 }
 return false;
}

Of course, using native methods you could achieve better performance.

Answer 4

This is similar to longest common subsequence See this. this code solves your issue.

function contains(masterString, subString) {
 if (findCommonSubsequence(masterString, subString) == subString)
 alert(true);
 else
 alert(false);
 }
 function findCommonSubsequence(a, b) {
 var table = [],
 aLen = a.length,
 bLen = b.length;
 squareLen = Math.max(aLen, bLen);
 // Initialize a table of zeros
 for (var i = 0; i <= squareLen ; i++) {
 table.push([]);
 for (var j = 0; j <= squareLen; j++) {
 table[i][j] = 0;
 }
 }
 // Create a table of counts
 for (var i = 1; i <= aLen; i++) {
 for (var j = 1; j <= bLen; j++) {
 if (a[i - 1] == b[j - 1]) {
 table[i][j] = table[i - 1][j - 1] + 1;
 } else {
 table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
 }
 }
 }
 // Move backwards along the table
 i = aLen, j = bLen, LCS = [];
 while (i > 0 && j > 0) {
 if (a[i - 1] == b[j - 1]) {
 LCS.push(a[i - 1]);
 i -= 1;
 j -= 1;
 } else {
 if (table[i][j - 1] >= table[i - 1][j]) {
 j -= 1;
 } else {
 i -= 1;
 }
 }
 }
 return(LCS.reverse().join(''));
 }

Answer 5

Your question doesn't have enough odd constraints, so let's do it without for-loops as well, with some help from ES6.

// Cf. Array.prototype.some
const any = (f, [x,...xs]) =>
 x === undefined ? false : f(x) || any(f,xs);
// Return true if the first iterable is a prefix of the second.
const isprefix = ([x,...xs], [y,...ys]) =>
 x === undefined ? true : x == y && isprefix(xs,ys);
// tails('abc') --> [['a','b','c'], ['b','c'], ['c']]
const tails = ([x,...xs]) =>
 x === undefined ? [] : [[x,...xs],...tails(xs)];
// If needle is empty, or is a prefix of any of tails(haystack), return true.
const contains = (haystack, needle) =>
 needle.length ? any(bale => isprefix(needle, bale), tails(haystack)) : true;
const tests = [
 ['aaafoobar', 'foo'],
 ['foo', 'foo'],
 ['fo', 'foo'],
 ['', 'f'],
 ['f', ''],
 ['', '']
];
tests.forEach(test => console.log(JSON.stringify(test), contains(test[0], test[1])));

• Vaibhav Pachauri: I could only accept one answer. But this implementation is great (y). Thanks again. +1
• 1983: No worries, I'm just glad you found it interesting. :-)

Answer 6

You can do like this

var substr = "test",
 masterstr = "test1",
checksubstr = (ms,ss) => !!~ms.indexOf(ss);
console.log(checksubstr(masterstr,substr));

• RomanPerekhrest: requirement - "without using any standard JavaScript methods"