x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 81

# javascript optimization on finding substrings

Hi Experts,

I have one string S that can be say, 200 characters long.   I have 10000 other strings that I want to see if they are in S.

My solution needs to work on IE9, IE10, IE11, Firefox and chrome.  I would preferably not like to use one method on one browser and another method for special case browsers that don't support functions.

What can I use to optimize this?

Thanks a lot!
Mike
0
2 Solutions

Software EngineerCommented:
The Knuth-Morris-Pratt algorithm is pretty quick and is O(S). That's about as good as you're going to get without getting overly complicated. You'll probably need to implement it in JS yourself.

``````algorithm kmp_search:
input:
an array of characters, S (the text to be searched)
an array of characters, W (the word sought)
output:
an integer (the zero-based position in S at which W is found)

define variables:
an integer, m ← 0 (the beginning of the current match in S)
an integer, i ← 0 (the position of the current character in W)
an array of integers, T (the table, computed elsewhere)

while m + i < length(S) do
if W[i] = S[m + i] then
if i = length(W) - 1 then
return m
let i ← i + 1
else
if T[i] > -1 then
let m ← m + i - T[i], i ← T[i]
else
let i ← 0, m ← m + 1

(if we reach here, we have searched all of S unsuccessfully)
return the length of S
``````
0

Software engineerCommented:
FYI: You'd better not tagged this question as a Java Programming language question.
Java and JavaScript are two different languages.
0

Commented:
greetings thready, , Not sure about exact nature of what you describe as "to see if they are in S", If all you need is a return of "TRUE" if array value IS in string, Then I believe that the -
for (s=0; s < seek.length; ++s)
if (str.indexOf(seek[s]) > -1) found[s] = true; else found[s] = false;

would be the most effective.
I found this in the AJAX section, not sure I see any reference to a server side response here? ?
0

Author Commented: