Solved

javascript optimization on finding substrings

Posted on 2015-02-10
4
68 Views
Last Modified: 2015-02-13
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
Comment
Question by:thready
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 Comments
 
LVL 8

Accepted Solution

by:
James Bilous earned 250 total points
ID: 40600938
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

Open in new window

0
 
LVL 37

Expert Comment

by:zzynx
ID: 40600939
FYI: You'd better not tagged this question as a Java Programming language question.
Java and JavaScript are two different languages.
0
 
LVL 34

Assisted Solution

by:Slick812
Slick812 earned 250 total points
ID: 40601589
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
 
LVL 1

Author Closing Comment

by:thready
ID: 40609265
Thanks a lot for your answers!
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

756 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question