Re: String matching & linear programming...

Maybe you're looking for suffix trees.
Take a look in wikipedia.

<almurph@xxxxxxxxxxxxx> ha scritto nel messaggio
news:983c7e59-4d3d-4f04-ba4e-ab630f3dea1e@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hi,

I want to develop an algorithm that at some stage uses a linear
programming technique to solve the string matching problem.
That is, say I have a string of the following format:
"ASWERFGTGSDWEFTSFSDWFDVGHNHJTT" and I want to find smaller string in
it like "SDWEFT" or anything *similar* like "SDEFT".

I'm wondering can this problem be posed in the form suitable for a
linear programming solution?

I would greatly appreciate any suggestions/comments/ideas/experiences
that you may have.

Thank you,
Al.



.

Relevant Pages

  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.math.research)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.physics.research)
  • Re: Attention Sean - question about CSI
    ... the best compression algorithm you have. ... It should compress very ... which compresses that string to a single bit. ... from the binary code, and use it to decompress the data, then ...
    (talk.origins)
  • Re: Optimize an IEnumerable
    ... Though, personally it seems to me that unless you have a very specific need to reuse the enumeration in completely different places in the code, it might be better to just have the _client_ of the enumerator cache the results as needed. ... foreach (string someThingToFind in _list) ... That is, yes it has the potential for improving performance, but it doesn't really change the efficiency of the algorithm. ... A common one used for string searches such as yours would be a state machine implementation, where the nodes of the state graph are connected according to the letters in the search words. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Regular Expression for validating a url field
    ... (Do not use the tab character for indentation, ... against a supposed string value, and since you do not do perform a strict ... If x is NaN, return false. ... `false' is returned to the calling algorithm, ...
    (comp.lang.javascript)