Sunday 算法（盡可能的移動最大長度）

Sunday算法是從前往后匹配抵栈，在匹配失敗時關(guān)注的是文本串中參加匹配的最末位字符的下一位字符

• 如果該字符沒有在主模式字符串中出現(xiàn)則跳過，移動位 = 匹配字符串長度 + 1
• 該字符在主模式字符串中出現(xiàn)，
  1)移動位 = 該字符在模式串中最后出現(xiàn)位置距末端長度 + 1
  2)移動位 = 模式串長度 - 該字符在模式串中最后出現(xiàn)位置

文本串第1個字符 s != 模式串第1個字符 e光酣，那么關(guān)注文本串中參加匹配的未位字符下一個字符： a

image.png

a 在 ea 字符串的最后一位遭殉，則移動位= 0 + 1 = 2（模式串長度） - 1（a 在模式串最后出現(xiàn)位置）= 1

image.png

image.png

匹配成功

代碼現(xiàn)實(shí)

<?php


namespace Patterns\Algorithm;

/**
 * 如果該字符沒有在主模式字符串中出現(xiàn)則跳過属拾，移動位 = 匹配字符串長度 + 1
 * 該字符在主模式字符串中出現(xiàn)航唆，
    1)移動位 = 該字符在模式串中最后出現(xiàn)位置距末端長度 + 1
    2)移動位 = 模式串長度 - 該字符在模式串中最后出現(xiàn)位置
 * Class Sunday
 * @package Patterns\Algorithm
 */
class Sunday
{
    public $_needleLen;
    public $_haystackLen;
    public $_table;

    /**
     * 返回 -1 表示無法匹配胀蛮，否則返回首次出現(xiàn)位置
     *
     * @param string $haystack
     * @param string $needle
     * @return int
     */
    public function strpos(string $haystack, string $needle):int
    {
        $this->_haystackLen = strlen($haystack);
        $this->_needleLen = strlen($needle);

        if($this->_needleLen > $this->_haystackLen){
            return null;
        }

        $this->prefixTable($needle);
        $p = $this->_haystackLen - $this->_needleLen;
        $s = 0;
        while ($s <= $p){
            $j = 0;
            while ($haystack[$s + $j] == $needle[$j]){
                $j += 1;
                if($j == $this->_needleLen){
                    return $s;
                }
            }

            $haystackIndex = $s + $this->_needleLen;
            if(!isset($haystack[$haystackIndex]))
                break;

            $hIndexText = $haystack[$haystackIndex];
            $s += (isset($this->_table[$hIndexText]) ? $this->_table[$hIndexText] : $this->_needleLen);
        }

        return -1;
    }

    /**
     * 匹配所有出現(xiàn)位置
     * @param string $haystack
     * @param string $needle
     * @return array
     */
    public function strapos(string $haystack, string $needle):array
    {
        $this->_haystackLen = strlen($haystack);
        $this->_needleLen = strlen($needle);

        if($this->_needleLen > $this->_haystackLen){
            return null;
        }

        $this->prefixTable($needle);
        $p = $this->_haystackLen - $this->_needleLen;
        $s = 0;

        $pos = [];
        while ($s <= $p){
            $j = 0;
            while (isset($needle[$j]) && $haystack[$s + $j] == $needle[$j]){
                $j += 1;
                if($j == $this->_needleLen){
                    array_push($pos, $s);
                }
            }

            $haystackIndex = $s + $this->_needleLen;
            if(!isset($haystack[$haystackIndex]))
                break;

            $hIndexText = $haystack[$haystackIndex];
            $s += (isset($this->_table[$hIndexText]) ? $this->_table[$hIndexText] : $this->_needleLen);
        }

        return $pos;
    }

    /**
     * 模式串字符表
     * @param string $needle
     */
    public function prefixTable(string $needle)
    {
        for($i=0; $i < $this->_needleLen; $i++){
            //字符最后出現(xiàn)的位置距末端長度：字符串長度 - 字符當(dāng)前位置
            $this->_table[$needle[$i]] = $this->_needleLen - $i;
        }

    }

}


$haystack = 'search title.';
$needle = 'w';

$obj = new Sunday();
$index = $obj->strpos($haystack, $needle);

echo $index . PHP_EOL;

var_export($obj->strapos($haystack, $needle));

echo strpos($haystack, $needle) . PHP_EOL;