Find longest common substring in a list?

Edit: I had posted an idea but then I re-read your post and realized I was not understanding the problem. If you could post a couple of example lists, that would help me understand the problem better.

Here is an example list

P20_C1_F1_R3__1903_036;P20_C1_F1_R3__1903_037;P20_C1_F1_R3__1903_038;P20_C1_F1_R3__1903_039;P20_C1_F1_R3__1903_040;

In this case, the SampleID = P20_C1_F1_R3__1903

The longest common substring would actually be P20_C1_F1_R3__1903_0 (due to the leading zero on the ReplicateID), but I can probably handle that downstream.

Another example is

P7_PRE_B;P7_1_A;P7_1_B;P7_2_A;P7_2_B;

Here SampleID = P7, which is also the longest substring after removal of the terminal "_".

If sampleID is always the start of each list item, you could take a simple brute-force approach and figure out how many characters it is until the strings don't match. E.g., the following seems to work if you run testit()

That indeed seems to do what I want.

Thanks.

If you have the name as a string wave you could sort the wave alphabetically with Sort and then find the longest common string of the first and last strings in the wave. That way you only have to compare two strings and not all of them.

olelytken wrote:

If you have the name as a string wave you could sort the wave alphabetically with Sort and then find the longest common string of the first and last strings in the wave. That way you only have to compare two strings and not all of them.

With Igor 7 or later you can use the ListToTextWave function to convert a string list into a text wave. However for the purposes of this question you could also just use SortList (probably on a copy of the string list) without first converting the string list into a text wave.

This incorporates the suggestion from Olelytken and Adam. It avoids an explicit for loop.

I had initially thought to build a version that built a string (wave) as rwstr = ... ? faster[p] : "". As noted in a separate thread, the logical comparison would use SelectString(cmpstr(...),fstr[p],""). I don't know of any advantages unless the string can be built directly rather than using a text wave that must then be converted back to a string.

This avoids an explicit loop, but implicitly iterates p over wave rwstr and strings fstr & lstr. Other than having more compact code is this still more efficient than a loop?

Using p instead of a for loop is usually faster. You could probably also multithread the p line, although I suspect the slowest bit in the code is the SortList line.

@topchem: How many items do you expect in the string list?

Not many. Probably a maximum of 20. 

With a few tens of sample folders.

I don't expect execution time to be an issue for my use case. I'm just always curious how different coding approaches scale.

By habit, I try to avoid explicit for loops when I can construct implicit ones. They should generally be faster and they are easier for me to debug visually.

When the strings in the list all have at least one character past a common prefix, you can eliminate the list sorting and choose any two of the items in the list (e.g. the first and last).

With only 20 list items I think the solution from jjweimer is fine. With more than a couple of thousands switchting to using textwaves instead could be faster.