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 :)

"...without using any standard JavaScript methods?" Why such a restriction? — Jeremy J Starcher
– Jeremy J Starcher, Commented May 24, 2016 at 19:46
I see no benefits of such approach: bad readability, bad flexibility, a lot of code ... perhaps, only testing for loop(just for fun) — RomanPerekhrest
– RomanPerekhrest, Commented May 24, 2016 at 19:57

RainingChain · Accepted Answer · 2016-05-24 19:47:48Z

5

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.

answered May 24, 2016 at 19:47

RainingChain

7,82210 gold badges39 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Simon Schüpbach · Accepted Answer · 2016-05-24 20:07:25Z

1

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'));

edited May 24, 2016 at 20:07

answered May 24, 2016 at 19:55

Simon Schüpbach

2,6833 gold badges15 silver badges26 bronze badges

1 Comment

Oriol Over a year ago

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

Oriol · Accepted Answer · 2016-05-24 19:53:46Z

1

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.

answered May 24, 2016 at 19:53

Oriol

291k71 gold badges459 silver badges535 bronze badges

Comments

Ali Soltani · Accepted Answer · 2016-05-24 20:11:11Z

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(''));
    }

1983 · Accepted Answer · 2016-11-09 22:44:58Z

1

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])));

edited Nov 9, 2016 at 22:44

answered May 24, 2016 at 20:37

1983

5,9832 gold badges30 silver badges39 bronze badges

2 Comments

Vaibhav Pachauri Over a year ago

I could only accept one answer. But this implementation is great (y). Thanks again. +1

1983 Over a year ago

No worries, I'm just glad you found it interesting. :-)

Redu · Accepted Answer · 2016-05-24 19:53:08Z

0

You can do like this

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

console.log(checksubstr(masterstr,substr));

edited May 24, 2016 at 19:53

answered May 24, 2016 at 19:49

Redu

26.3k6 gold badges61 silver badges84 bronze badges

1 Comment

RomanPerekhrest Over a year ago

requirement - "without using any standard JavaScript methods"

Collectives™ on Stack Overflow

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

6 Answers 6

Comments

1 Comment

Comments

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

1 Comment

Comments

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related