How do I get the longest possible common prefix between an array of strings?

See more:

C#6.0

C#7.0

I don't mean the common prefix between all of them.

I mean for

ABaC
ABaD
AaC
Aad
CD
Cc

I want the routine to give me (ABa)

and then i want to be able to pass the remainder to the routine (sans the first two entries that had that prefix)

AaC
Aad
CD
Cc

And the routine should give me Aa

and if I do it again with the previous matches ommitted (this list)

CD
Cc


the routine should give me C

Here's the catch. The list cannot be sorted. These aren't really strings. You can treat them as strings but the characters can only be compared for ==, not for > or <

for reasons i could get into, but it's a functional requirement. I don't care how badly the operation performs.



I'll accept C#, java, or maybe javascript if you don't get crazy with it and use functor things all over the place. No LINQ please

What I have tried:

var groupsStart = new Dictionary<IList<object>, IList<IList<object>>>(OrderedCollectionEqualityComparer<object>.Default);
			foreach (var flatRule in flatRules)
			{
				foreach (var flatRuleCmp in flatRules)
				{
					var common = new IList<object>[] { flatRule.Key, flatRuleCmp.Key }.GetCommonPrefix();
					if (0 == common.Count)
						continue;
					IList<IList<object>> list;
					if (!groupsStart.TryGetValue(common, out list))
					{
						list = new List<IList<object>>();
						groupsStart.Add(common, list);
					}
					if(!list.Contains(flatRuleCmp.Key,OrderedCollectionEqualityComparer<object>.Default))
						list.Add(flatRuleCmp.Key);

				}
			}

I said they weren't really strings. (but treat them that way here, since it's easier)

Basically i tried enumerating the list and finding common prefixes as above, but it didn't work. It only kinda worked. I keep knowing how to do it, but then blanking out when it comes to write the thing. It has been one of those afternoons.

whooops, I think it might be this simple. Testing

public static IList<T> GetLongestCommonPrefix<T>(this IEnumerable<IList<T>> ss)
{
	IList<T> result = null;
	foreach(var list in ss)
	{
		foreach(var list2 in ss)
		{
			if (!ReferenceEquals(list, list2))
			{
				var pfx = GetCommonPrefix<T>(new IList<T>[] { list, list2 });
				if (null == result || (null != pfx && pfx.Count > result.Count))
					result = pfx;
			}
		}
	}
	return result;
}