0
$\begingroup$

I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting to implement a method that searches for a specific (given) value and returns the Section object(s) it found the value in. There are however two different scenarios as described below.

Value: restaurant

Scenario 1

  1. "John went to the restaurant to pick " ✔️

  2. "up the food he ordered online before "

  3. "he went to his mother's house."

Current behaviour: Found in Section 1

Desired behaviour: Found in Section 1

Scenario 2

  1. "John went to the restaura"

  2. "nt to pick up the food he ord"

  3. "ered online before he went to his mother's house."

Current behaviour: Couldn't find the value

Desired behaviour: Found in list(Section 1, Section 2)


Scenario 1 is easily solved as the value is found completely in section 1. In the 2nd scenario, the value is never found as it is split up between sections. I have written an algorithm that tries to stitch these sections together. It appears to work when the given value is simple e.g., "car" or "boat". I'm having troubles with compound strings such as "the supermarket" or "a green flower". I wrote the code a couple of months ago and tried debugging it, but even I fail to understand my own code here.

I deliberately left my code out of this post as it has rough hardcoded rules and has extreme levels of code complexity. I'd like to rethink the algorithm without looking at the current one to refrain from blatantly copying sections of the existing code.

The code is written in Java in case anyone knows some handy Java functions that might help.

$\endgroup$
4
  • $\begingroup$ If the number of lines is very small, you could just try all pairs. $\endgroup$ May 22, 2020 at 10:54
  • $\begingroup$ @YuvalFilmus In theory, it can range from 2 lines to a couple of thousand lines $\endgroup$
    – Arjan
    May 22, 2020 at 10:57
  • $\begingroup$ Another think to try is to look for suffixes of your word at the beginning of lines, and prefixes of your word at the end of lines. $\endgroup$ May 22, 2020 at 10:58
  • $\begingroup$ @YuvalFilmus That's what I'm doing right now matching individual characters until the value is found, otherwise I start over looking for a matching 1st character and repeating $\endgroup$
    – Arjan
    May 22, 2020 at 11:04

2 Answers 2

1
$\begingroup$

If all the words are going to be English words, you can run all the words through a dictionary. If you find any non-dictionary words at the start or end of the sections and you are unable to find the "key", you can just combine those words until the key is found.

Alternatively, you can trivially just combine the the words (once) at the start/end of sections until the word is found. I don't believe this will to too inefficient computationally since the described sections are quite large.

$\endgroup$
0
$\begingroup$

First , you'll have to create a List<String> , which will contains all possible substrings of your desired value , then you will search if any of the lines contains at least one of the elements of the list

  • Example :

value : "abc"

List of possible susbtrings : { "a" , "b" , "c" , "ab" , "bc" , "abc" }

The phrases : { "I want to find ab" , "c here it is" }

The 2 phrases contains "ab" and "c" , their concatenation is equal to the value , so the phrases contains the value

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.