0

Recently I was asked in an interview, where the interviewer asked me this above question.

I was surely perplexed and answered him by using a for loop implementation where

  1. we would find the length of the given "text" (using JavaScript) ... str.length() ...
  2. we would take the first element of the "pattern" and find that in the "text".
  3. If found we would increment the array .. As strings are stored as array in JavaScript ..
  4. And we would find the "(a substring)" in similar way..

know this might be wrong way , but can anyone suggest a better way ? Thank you :-)

Improve this question
15
  • 2
    string.indexOf Commented Feb 9, 2014 at 23:58
  • Internally, I would suspect that is what's happening. How else can you find a pattern in a given set of text without iterating over the characters. If the pattern is simple, you can use some type of contains or indexOf function. Commented Feb 9, 2014 at 23:58
  • He said write a code for Regular Expression itself .. Means to write a code for str.match() .. Using no inbuilt function .. Make your own function Commented Feb 10, 2014 at 0:01
  • There is a difference between a pattern and a substring. You question is not fully accurate Commented Feb 10, 2014 at 0:03
  • 1
    Write it in pseudocode. Did he specify a language? Commented Feb 10, 2014 at 0:09

2 Answers 2

Reset to default
1

String.prototype.search (regexp)

When the search method is called with argument regexp, the following steps are taken:

  1. Call CheckObjectCoercible passing the this value as its argument.

  2. Let string be the result of calling ToString, giving it the this value as its argument.

  3. If Type(regexp) is Object and the value of the [[Class]] internal property of regexp is "RegExp", then let rx be regexp;

  4. Else, let rx be a new RegExp object created as if by the expression new RegExp(regexp) where RegExp is the standard built-in constructor with that name.

  5. Search the value string from its beginning for an occurrence of the regular expression pattern rx. Let result be a Number indicating the offset within string where the pattern matched, or –1 if there was no match. The lastIndex and global properties of regexp are ignored when performing the search. The lastIndex property of regexp is left unchanged.

  6. Return result.

Or if you want to avoid the word RegExp alltogether and search for a sub-string then

String.prototype.indexOf (searchString, position)

If searchString appears as a substring of the result of converting this object to a String, at one or more positions that are greater than or equal to position, then the index of the smallest such position is returned; otherwise, ‑1 is returned. If position is undefined, 0 is assumed, so as to search all of the String.

The indexOf method takes two arguments, searchString and position, and performs the following steps:

  1. Call CheckObjectCoercible passing the this value as its argument.

  2. Let S be the result of calling ToString, giving it the this value as its argument.

  3. Let searchStr be ToString(searchString).

  4. Let pos be ToInteger(position). (If position is undefined, this step produces the value 0).

  5. Let len be the number of characters in S.

  6. Let start be min(max(pos, 0), len).

  7. Let searchLen be the number of characters in searchStr.

  8. Return the smallest possible integer k not smaller than start such that k+ searchLen is not greater than len, and for all nonnegative integers j less than searchLen, the character at position k+j of S is the same as the character at position j of searchStr; but if there is no such integer k, then return the value -1.

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

Comments

0

I think the answer depends on the context, and the context seems to be lacking.

If the question was about algorithms, then I believe your best choice of algorithms (i.e., the fastest algorithm) is Boyer–Moore string search.

If the question was a HowTo in PHP, then its probably string.indexOf. And str.search would probably not be a valid answer since it takes a regex.

  1. S[i] refers to the character at index i of string S, counting from 1.
  2. S[i..j] refers to the substring of string S starting at index i and ending at j, inclusive.
  3. A prefix of S is a substring S[1..i] for some i in range [1, n], where n is the length of S.
  4. A suffix of S is a substring S[i..n] for some i in range [1, n], where n is the length of S.
  5. The string to be searched for is called the pattern and is referred to with symbol P.
  6. The string being searched in is called the text and is referred to with symbol T.
  7. The length of P is n.
  8. The length of T is m.
  9. An alignment of P to T is an index k in T such that the last character of P is aligned with index k of T.
  10. A match or occurrence of P occurs at an alignment if P is equivalent to T[(k-n+1)..k].
Improve this answer

2 Comments

I had to use NO functions !!:( .. Just basic for loop and something like that ..
Your question does not state "NO functions". It only states "without using regular expressions" (and that's in the title). But you still have the Boyer-Moore string search algorithm.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.