PDA

View Full Version : Algorithm for comparing word with randomly distributed substring



asdf1234
07-01-2014, 03:12 AM
Hello,

I'm facing a strange problem. I have a word for example "ABCDE". I want to match this word againsta sentence like "ABC EFGH IJKL DE". As you can see, the query word is splited and distributed across the senetence. How can I design algorithm which can give me result like the query word has acombination in the sentence and their position.


An example;

QUERY word: ABCDEF
TARGET sentence: EFGH UIOP ABC GHY JKLU EF

I expect the output as the query word has a perfect match by the combining words 3,6.

I tried several algorithms like smithwatermann, levenstein distance and others, but I could figure out how I can compare string with randomly distributed sub-strings in a sentence.


One way of doing is, breaking sentence into words and make all possible combinations and start matching with query which would take forever if I have 500 words.

Any help or suggestion would be highly appreciated.

Aleksandar
07-01-2014, 03:34 AM
And how is your question related to OpenGL? :confused: