Algorithm for comapring word with randomly distributed substring
-
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.