so, I have a ragged array (called names) of length 200. each pointer in the array points to a string that is no longer than 50 characters and has no white spaces. I also have a string given through user-input called inname, with length 50, inname will be one of the strings stored in names. I need to find a way to go through the strings in my ragged array and find the string with the largest substring overlap with inname, excluding inname itself as that will be in the file. If no string has an overlap then we print out "no recommendation". I've been melting trying to puzzle this out for many hours now, helps? O:) SO basically, the program finds the name in the array with the largest substring overlap with inname. will edit to provide additional info if you need it
问题:
回答1:
This won't lead you to the most efficient way to find overlap (dynamic programming is one way--there are other crazy methods like suffix trees), but it should get you started:
First, think about how you would find the length of the overlap with the beginning of both strings aligned. For instance, find the longest overlap between these two:
programming
ungrammatical
In this case, only a single m overlaps--a length of 1.
Then think about how you would "shift" the strings and look for the overlap when they are aligned differently. (Don't actually change the strings: just change how you loop through them to compare them.) What is the overlap between these two?
programming
ungrammatical
Think about how to look at all possible alignments. If you keep track of the longest one you find, you have the longest alignment between two particular strings.
After that, move on to checking all the different strings. Keep track of the one with the best match, and again, once you have looked at all of them, you have your answer.
回答2:
You should probably start on the smaller problem of determining the size of the overlap between infunc and a single string.
Wikipedia goes over some algorithms for solving the longest common substring problem (including pseudocode!)
