What data structure/aglorithm to use for strings to see if there

>>60311708
>>60311708
Are you..
Are you trying to do A7 for Hughes?

> see if there exists two strings you can concatenate to get a target?

NP complete, certificate is the two strings.

>>60312218
What is A7 and who is Hughes

File: 1465915875298.jpg (55KB, 719x960px) Image search: [Google]

55KB, 719x960px

>>60311708
Why a sorted array?
Why not use a HashSet to look for prefixes and then suffixes?
And lastly, why not use substrings of your target string as a vantage point for finding these prefixes, rather than iterating over a bunch of strings that may not even qualify as substrings?

File: 1485214438485.jpg (119KB, 850x850px) Image search: [Google]

119KB, 850x850px

>>60311708
>>60315925
This here is what I was thinking

    public String[] ayy(HashSet<String> strPool, String target) {
        for (int i = 1; i < target.length(); i++) {
            //find prefix
            String s1 = target.substring(0, i);
            if (strPool.contains(s1) == false) {
                continue;
            }
            
            //find suffix
            String s2 = target.substring(i);
            if (strPool.contains(s2)) {
                return new String[]{s1, s2};
            }
        }
        
        return null;
    }

>>60311708
The brute force approach would be:
get a set of strings and a target.
Make a set S1 of all the strings in the set that are prefixes of the target.
Make a set S2 of all the strings in the set that are suffixes of the target.
Then try to find a match:
For each string in s1, search for a matching suffix in s2. You could optimize it by only looking
at those suffixes in s2 that have the right length for your candidate in s1.

I haven't implemented it, but it seems like it could be efficient enough depending on how many strings are in your set.


>60313037
>NP complete, certificate is the two strings.
That's not how you show something is NP complete.

File: 1469289593647.jpg (68KB, 600x450px) Image search: [Google]

68KB, 600x450px

>>60317103
You only need a single set
See >>60316756

>>60317325
Post more cats

File: 1471700728374.jpg (54KB, 500x375px) Image search: [Google]

54KB, 500x375px

>>60317386
I'm running out of cute non-reaction ones.

>>60311708
Make a hashmap of all the strings in your program, then take the new string, split it in two at the middle and check if each part is in the hash, if they aren't, split one character over/under and try again.

File: 1476163712913.gif (2MB, 400x332px) Image search: [Google]

2MB, 400x332px

>>60317501
You would only be using the keyset of the hashmap, so just using a hashset is enough.