搜索字符串中的模式

Question

字符串中的模式搜索。

例如。

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

函数应返回0

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

Answer 1

你在这里能有什么概念可以用一个滑动窗口来解决。对于您的示例，您有一个大小为3的滑动窗口。

对于字符串中的每个字符，将当前字符的子字符串和接下来的两个字符作为当前模式。然后将窗口向上滑动一个位置，并检查字符串的其余部分是否具有当前模式包含的内容。如果是，则返回当前索引。如果没有，请重复。

实施例：

1010101101 
|-| 

所以，图案= 101。现在，我们通过一个字符前进的滑动窗口：

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

应当指出的是，这肯定不是最有效的算法或实现，但它应该有助于澄清问题并就如何解决这个问题给出一个简单的例子。基于该str_split documentation

Answer 2

，呼吁str_split上"1010101101"将导致：

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

这一切都不会相互匹配。

您需要查看字符串的每个3长切片（从索引0开始，然后索引为1，依此类推）。

我建议在看substr，你可以使用这样的：

substr($input_string, $index, $length) 

而且它可以把你的$input_string的部分开始长度$length的$index。

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

Answer 4

快速和肮脏的执行这样的模式搜索：

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; 

Answer 5

如果我正确理解你，你的问题归结为找出一个字符串中是否有三个字符的子字符串出现两次而没有重叠。这会让你第一次发生的位置，如果它：

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

或者我错过了什么吗？