-2

文字列内のパターン検索。

たとえば。

$string = "111111110000";
FindOut($string);

関数は 0 を返す必要があります

function FindOut($str){    
    $items =  str_split($str, 3);    
    print_r($items);
}
4

5 に答える 5

2

私があなたを正しく理解していれば、あなたの問題は、文字列内に 3 文字の部分文字列が重複せずに 2 回出現するかどうかを調べることに帰着します。これにより、次の場合に最初に出現した位置が取得されます。

function findPattern($string, $minlen=3) {
    $max = strlen($string)-$minlen;
    for($i=0;$i<=$max;$i++) {
        $pattern = substr($string,$i,$minlen);
        if(substr_count($string,$pattern)>1)
            return $i;
    }
    return false;
}

それとも、ここで何か不足していますか?

于 2012-11-12T19:03:13.513 に答える
1

ここにあるものは、スライディング ウィンドウで概念的に解決できます。あなたの例では、サイズ 3 のスライディング ウィンドウがあります。

文字列内の各文字について、現在の文字の部分文字列と次の 2 文字を現在のパターンとして取得します。次に、ウィンドウを 1 つ上の位置にスライドさせ、文字列の残りの部分に現在のパターンが含まれているかどうかを確認します。存在する場合は、現在のインデックスを返します。そうでない場合は、繰り返します。

例：

1010101101
|-|

したがって、パターン = 101. ここで、スライディング ウィンドウを 1 文字進めます。

1010101101
 |-|

そして、残りの文字列に が含まれているかどうか101を確認し、3 文字のすべての組み合わせをチェックします。

概念的には、この問題を解決するために必要なのはこれだけです。

編集:人々が単にコードを要求するのは本当に好きではありませんが、これは興味深い問題のように思えたので、上記のアルゴリズムの実装を以下に示します。これにより、ウィンドウ サイズを変更できます (3 に固定する代わりに、関数は簡単にテストされているだけで、明らかなエラー チェックは省略されています):

function findPattern( $str, $window_size = 3) {
    // Start the index at 0 (beginning of the string)
    $i = 0;

    // while( (the current pattern in the window) is not empty / false)
    while( ($current_pattern = substr( $str, $i, $window_size)) != false) {
        $possible_matches = array();

        // Get the combination of all possible matches from the remainder of the string
        for( $j = 0; $j < $window_size; $j++) {
            $possible_matches = array_merge( $possible_matches, str_split( substr( $str, $i + 1 + $j), $window_size));
        }

        // If the current pattern is in the possible matches, we found a duplicate, return the index of the first occurrence
        if( in_array( $current_pattern, $possible_matches)) {
            return $i;
        }

        // Otherwise, increment $i and grab a new window
        $i++;
    }
    // No duplicates were found, return -1
    return -1;
}

これは確かに最も効率的なアルゴリズムや実装ではありませんが、問題を明確にし、解決方法の簡単な例を示すのに役立つはずです。

于 2012-11-12T18:52:49.733 に答える
1

部分文字列関数を使用して、3 つに分割するだけでなく、3 文字ごとに歩いてチェックしたいようです。

function fp($s, $len = 3){
  $max = strlen($s) - $len; //borrowed from lafor as it was a terrible oversight by me
  $parts = array();

  for($i=0; $i < $max; $i++){
    $three = substr($s, $i, $len);
    if(array_key_exists("$three",$parts)){
          return $parts["$three"];  
    //if we've already seen it before then this is the first duplicate, we can return it
    }
    else{
      $parts["$three"] = i; //save the index of the starting position.
    }
  }

  return false; //if we get this far then we didn't find any duplicate strings
}
于 2012-11-12T18:57:39.457 に答える
0

そのようなパターン検索の迅速で汚い実装:

function findPattern($string){
    $matches = 0;
    $substrStart = 0;

    while($matches < 2 && $substrStart+ 3 < strlen($string) && $pattern = substr($string, $substrStart++, 3)){
        $matches = substr_count($string,$pattern);
    }

    if($matches < 2){
        return null;
    }
    return $substrStart-1;
于 2012-11-12T18:59:23.167 に答える
0

str_splitdocumentationに基づいて、str_splitonを呼び出すと、次のように"1010101101"なります。

Array(
  [0] => 101
  [1] => 010
  [2] => 110
  [3] => 1
}

これらのどれも互いに一致しません。

文字列の 3 つの長さの各スライスを調べる必要があります (インデックス 0 から開始し、次にインデックス 1 など)。

substr次のように使用できる を参照することをお勧めします。

substr($input_string, $index, $length)

そして、 lengthで$input_string始まるセクションを取得します。$index$length

于 2012-11-12T18:53:48.160 に答える