Solved

javascript optimization on finding substrings

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

Accepted Solution

by:
James Bilous earned 250 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Thanks a lot for your answers!
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Introduction HyperText Transfer Protocol (http://www.ietf.org/rfc/rfc2616.txt) or "HTTP" is the underpinning of internet communication.  As a teacher of web development I have heard many questions, mostly from my younger students who have come to t…
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 basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
The viewer will learn how to implement Singleton Design Pattern in Java.

771 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

10 Experts available now in Live!

Get 1:1 Help Now