2

我需要开发一种有效的算法来确定给定具有重复内容（并且仅重复内容）的字符串的唯一（重复）字符串...

例如：

"AbcdAbcdAbcdAbcd"=>"Abcd"

"Hello"=>"Hello"

我在想出一个相当有效的算法时遇到了一些麻烦；任何意见将不胜感激。

澄清：我想要最短的字符串，当重复足够多次时，等于总字符串。

4

6 回答 6

3 
    private static string FindShortestRepeatingString(string value)
    {
        if (value == null) throw new ArgumentNullException("value", "The value paramter is null.");

        for (int substringLength = 1; substringLength <= value.Length / 2; substringLength++)
            if (IsRepeatingStringOfLength(value, substringLength))
                return value.Substring(0, substringLength);
        return value;
    }

    private static bool IsRepeatingStringOfLength(string value, int substringLength)
    {
        if (value.Length % substringLength != 0)
            return false;
        int instanceCount = value.Length / substringLength;
        for (int characterCounter = 0; characterCounter < substringLength; characterCounter++)
        {
            char currentChar = value[characterCounter];
            for (int instanceCounter = 1; instanceCounter < instanceCount; instanceCounter++)
                if (value[instanceCounter * substringLength + characterCounter] != currentChar)
                    return false;
        }
        return true;
    }
于 2012-12-03T21:15:21.087 回答
1

像这样的东西：

public string ShortestRepeating(string str)
{
    for(int len = 1; len <= str.Length/2; len++)
    {
        if (str.Length % len == 0)
        {
            sub = str.SubString(0, len);
            StringBuilder builder = new StringBuilder(str.Length)
            while(builder.Length < str.Length)
                builder.Append(sub);
            if(str == builder.ToString())
                return sub;
        }
    }
    return str;
}

这只是从头开始查看子字符串，然后重复它们以查看它们是否匹配。它还会跳过任何长度不均匀地划分为原始字符串长度并且仅上升到 length / 2 的任何内容，因为超过该长度的任何内容都不能成为重复的候选对象。

于 2012-12-03T21:06:32.997 回答
1

也许这可以工作：

static string FindShortestSubstringPeriod(string input)
{
  if (string.IsNullOrEmpty(input))
    return input;

  for (int length = 1; length <= input.Length / 2; ++length)
  {
    int remainder;
    int repetitions = Math.DivRem(input.Length, length, out remainder);        
    if (remainder != 0)
      continue;
    string candidate = input.Remove(length);
    if (String.Concat(Enumerable.Repeat(candidate, repetitions)) == input)
      return candidate;
  }
  return input;
}
于 2012-12-03T21:11:27.203 回答
0

我会用这样的东西：

private static string FindRepeat(string str)
{
    var lengths = Enumerable.Range(1, str.Length - 1)
        .Where(len => str.Length % len == 0);

    foreach (int len in lengths)
    {
        bool matched = true;

        for (int index = 0; matched && index < str.Length; index += len)
        {
            for (int i = index; i < index + len; ++i)
            {
                if (str[i - index] != str[i])
                {
                    matched = false;
                    break;
                }
            }
        }

        if (matched)
            return str.Substring(0, len);
    }

    return str;
}
于 2012-12-03T21:22:33.170 回答
0

试试这个正则表达式：

^(\w*?)\1*$

它捕获尽可能少的字符，其中捕获的序列（并且仅捕获的序列）重复 0 次或更多次。根据 Jacob 的回答，您可以在之后的捕获中获取最短匹配的文本。

于 2012-12-04T14:35:03.253 回答
-1

您可以使用带有反向引用的正则表达式。

Match match = Regex.Match(@"^(.*?)\0*$");
String smallestRepeat = match.Groups[0];
于 2012-12-03T21:08:20.350 回答