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

多分これはうまくいくかもしれません：

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 に答える
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;
}

これは、最初から部分文字列を調べ始め、それらを繰り返して一致するかどうかを確認します。また、元の文字列の長さに均等に分割されない長さを持たないものもスキップし、長さ / 2 までしか上がりません。

于 2012-12-03T21:06:32.997 に答える
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 回以上繰り返される場合、できるだけ少ない文字をキャプチャします。ジェイコブの答えに従って、後でキャプチャから最短一致のテキストを取得できます。

于 2012-12-04T14:35:03.253 に答える
-1

後方参照で正規表現を使用できます。

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