如何在字符串数组之间获得尽可能长的公共前缀？ [英] How do I get the longest possible common prefix between an array of strings?

问题描述

我不是指所有人之间的共同前缀。



我的意思是



ABaC

ABaD

AaC

Aad

CD

Cc


我希望例程给我（ABa）



然后我希望能够通过其余的例程（没有前缀的前两个条目）



AaC

Aad

CD

Cc



例程应该给我Aa



如果我以前的比赛省略了（这个清单）



CD

Cc





例程应该给我C



这是捕获。列表无法排序。这些不是真正的字符串。您可以将它们视为字符串，但只能比较==的字符，而不是>或者<



由于我可以进入的原因，但这是一个功能要求。我不在乎操作有多糟糕。







我会接受C＃，java ，或者javascript，如果你不对它疯狂，并在各处使用仿函数的东西。没有LINQ请



我尝试过：

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);

				}
			}

我说他们不是真正的字符串。 （但在这里对待它们，因为它更容易）



基本上我尝试枚举列表并找到如上所述的公共前缀，但它不起作用。它只是有点工作。我一直都知道如何去做，但是在写这个东西的时候就会搞清楚。这是下午之一。



whooops，我想这可能就是这么简单。测试

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;
}

推荐答案

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;
}

这篇关于如何在字符串数组之间获得尽可能长的公共前缀？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！