Solved

javascript optimization on finding substrings

Posted on 2015-02-10
4
64 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
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 33

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
This video teaches viewers about errors in exception handling.

862 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

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now