6

2 進数の文字列で繰り返しパターンを見つけようとしています。

例えば。0010010010 または 1110111011 = OK

いいえ。0100101101 = 悪い

文字列は（上記のように）10桁の長さで、「パターン」の2回の反復が最小であると思います。

プログラムが照合できるパターンの「バンク」を手動で設定し始めましたが、アルゴリズムを使用するより良い方法があるはずですか?

検索してもどこにも行きません - 使用している言語と用語が間違っていると思います..

4

7 に答える 7

2

かなりの挑戦です。この機能はどうですか？

function findPattern(n) {
    var maxlen = parseInt(n.length/2);
    NEXT:
    for(var i=1; i<=maxlen; ++i) {
        var len=0, k=0, prev="", sub;
        do {
            sub = n.substring(k,k+i);
            k+= i;
            len = sub.length;
            if(len!=i) break;
            if(prev.length && sub.length==i && prev!=sub) continue NEXT;
            if(!prev.length) prev = sub;
        } while(sub.length);
        var trail = n.substr(n.length-len);
        if(!len || len && trail==n.substr(0,len)) return n.substr(0,i);
    }
    return false;
}

どんな内容のどんな長さの文字列でも機能します。フィドルを見る

Jack's and Zim-Zam's answer に触発されたブルート フォース アルゴリズムのリストを次に示します。

var oksubs =
["001","010","011","100","101","110",
"0001","0010","0011","0100","0101","0110","0111",
"1000","1001","1010","1011","1100","1101","1110",
"00000","00001","00011","00101","00110","00111","01000",
"01001","01010","01011","01100","01101","01110","01111",
"10000","10001","10011","10101","10110","10111","11000","11001",
"11010","11011","11100","11101","11110","11111"];

ジャックのコメントのおかげで、ここに短くて効果的なコードがあります。

function findPattern(n) {
    var oksubs = [n.substr(0,5),n.substr(0,4),n.substr(0,3)];
    for(var i=0; i<oksubs.length; ++i) {
        var sub = oksubs[i];
        if((sub+sub+sub+sub).substr(0,10)==n) return sub;
    }
    return false;
}
于 2013-05-10T05:01:57.930 に答える
1

2^10 パターンしかありません。これは、すべての有効な文字列を事前に計算し、結果を 1024 要素のブール配列に格納できるほど十分に小さい数です。文字列が有効な場合は、それを整数 (例: "0000001111" = 15) に変換し、結果の配列インデックスに "true" を格納します。文字列が有効かどうかを確認するには、文字列を整数に変換し、事前に計算されたブール配列でインデックスを検索します。

文字列が 10 桁を超える場合は、文字列が有効かどうかを判断するのにもっと賢くする必要がありますが、文字列が 1024 個しかないので、これについては怠惰になるかもしれません。

于 2013-05-10T04:02:22.393 に答える
1

私が知る限り、長さ 10 => の 62 のパターン化されたバイナリ文字列があります2^1 + 2^2 + 2^3 + 2^4 + 2^5。それらをリストし、パターン化された文字列と一致するコードを次に示します。

function binComb (n){
  var answer = []
  for (var i=0; i<Math.pow(2,n);i++){
    var str = i.toString(2)
    for (var j=str.length; j<n; j++){
      str = "0" + str
    }
    answer.push(str)
  }
  return answer
}

function allCycles(){
  var answer = {}, cycled = ""
  for (var i=1; i<=5; i++){
    var arr = binComb(i)
    for (var j=0; j<arr.length; j++){
      while(cycled.length < 10){
        cycled += arr[j]
        if (10 - cycled.length < arr[j].length)
          cycled += arr[j].substr(0,10 - cycled.length)
      }
      if (answer[cycled]) 
        answer[cycled].push(arr[j])
      else answer[cycled] = [arr[j]]
      cycled = ""
    }
  }
  return answer
}

function getPattern (str){
  var patterns = allCycles()
  if (patterns[str]) 
    return patterns[str]
  else return "Pattern not found."
}

出力：

console.log(getPattern("0010010010"))
console.log(getPattern("1110111011"))
console.log(getPattern("0100101101"))
console.log(getPattern("1111111111"))

["001"]
["1110"]
Pattern not found.
["1", "11", "111", "1111", "11111"]
于 2013-05-10T13:31:25.723 に答える
1
  1. 2^10 の配列を維持することは、どの文字列が繰り返しパターンを持っているかを示さないため、役に立ちません。

  2. 繰り返しパターンを作成するには、パターンの長さを 5 以下にする必要があります

  3. 長さ 1 のパターンが存在する可能性がありますが、長さ 5 のパターンがそれをカバーします。[ステップ編集]

  4. 長さ 2 のパターンがある場合、常に長さ 4 のパターンがあります。

  5. (1)、(2)、(3)、(4) から、長さ 3、4、5 のパターンのみをチェックする必要があります。

  6. つまり、最初の 3 桁が次の 3 桁と一致する場合は、文字列の終わりまで進み、そうでない場合はブレークして 7 に進みます

  7. そうでなければ最初の 4 桁を次の 4 桁と一致させる if 一致は文字列の最後まで続行する else ブレークして 8 に進む

  8. そうでなければ最初の 5 桁を次の 4 桁と一致させる if 一致は文字列の最後まで続行する else ブレークして 9 に進む

  9. 6、7、8 のいずれかが false の場合、failure を返します

于 2013-05-10T05:42:18.197 に答える
1

私のブルートフォースアプローチは次のようになります。

例によって

  1. 与えられた文字列: 0010010010:

  2. givenString の可能なパターンのリストを作成します0010010010。

    possiblePatterns = [00, 010, 0010, 00100, 01, 001, 0100, 10, 100]

  3. それらを繰り返して、長さ>= 10の文字列を作成します

    testPattern0 = 0000000000    // 00 00 00 00 00
testPattern1 = 010010010010  // 010 010 010 010
testPattern2 = 001000100010  // 0010 0010 0010
...

  4. そしてチェック...

    for each testPattern:
    if '0010010010' is a substring of testPattern ==> pattern found

    一致する文字列の 1 つ:

    testPattern2: 010010010010
givenString :   0010010010

  5. 見つかったパターン:

    foundPatterns = [010, 001, 100]

ご覧のとおり、すべてのパターンは基本的に同じで、シフトされているだけなので、これは冗長なリストである可能性があります。ただし、ユースケースによっては、これが実際に必要な場合があります。

コード：

function findPatterns(str){
    var len = str.length;
    var possible_patterns = {};  // save as keys to prevent duplicates
    var testPattern;
    var foundPatterns = [];

    // 1) create collection of possible patterns where:
    //    1 < possiblePattern.length <= str.length/2
    for(var i = 0; i <= len/2; i++){
        for(var j = i+2; j <= len/2; j++){
            possible_patterns[str.substring(i, j)] = 0;
        }
    }

    // 2) create testPattern to test against given str where:
    //    testPattern.length >= str.length
    for(var pattern in possible_patterns){
        testPattern = new Array(Math.ceil(len/pattern.length)+1).join(pattern);
        if(testPattern.indexOf(str) >= 0){
            foundPatterns.push(pattern);
        }
    }
    return foundPatterns;
}

==>フィドル

于 2013-05-10T05:08:14.010 に答える
0

Python (再び) では、正規表現なし:

def is_repeated(text):
    'check if the first part of the string is repeated throughout the string'
    len_text = len(text)
    for rep_len in range(len_text // 2,  0, -1):
        reps = (len_text + rep_len) // rep_len
        if (text[:rep_len] * reps).startswith(text):
            return rep_len  # equivalent to boolean True as will not be zero
    return 0     # equivalent to boolean False

matchstr = """\
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
"""
for line in matchstr.split():
    print('%r has a repetition length of %i' % (line, is_repeated(line)))

出力：

'1001110011' has a repetition length of 5
'1110111011' has a repetition length of 4
'0010010010' has a repetition length of 3
'1010101010' has a repetition length of 4
'1111111111' has a repetition length of 5
'0100101101' has a repetition length of 0
于 2013-05-10T06:49:02.173 に答える