字符串匹配

性质

给定模式集合，和源集合。算法输出源集合中和模式匹配的所有相关处的起始位置。

接口设计

template
   
    class CharacterMatch{public:	CharacterMatch();	~CharacterMatch();public:	DataStruct::Array::DynArray
    
      RunInAutoMachine(		const DataStruct::Array::DynArray
     
      & arrPattern_,		const DataStruct::Array::DynArray
      
       & arrSource_);};

实现

构造

template
   
    CharacterMatch
    
     ::CharacterMatch(){}

析构

template
   
    CharacterMatch
    
     ::~CharacterMatch(){}

算法运行

template
   
    DataStruct::Array::DynArray
    
      CharacterMatch
     
      ::RunInAutoMachine(	const DataStruct::Array::DynArray
      
       & arrPattern_,	const DataStruct::Array::DynArray
       
        & arrSource_){	int _nPatternLen = arrPattern_.GetSize();	int _nSourceLen = arrSource_.GetSize();	int _nPreMaxMatchLen = 0;	int _nCurMaxMatchLen = 0;	DataStruct::Array::DynArray
        
          _arrRet; for (int _i = 0; _i < _nSourceLen; _i++) { if (_nPreMaxMatchLen == _nPatternLen) { for (int _nCurMayMaxMatchLen = _nPreMaxMatchLen; _nCurMayMaxMatchLen >= 0; _nCurMayMaxMatchLen--) { bool _bSuccess = true; int _k = 0; while (_k < _nCurMayMaxMatchLen) { if (arrSource_[_i - _k] == arrPattern_[_nCurMayMaxMatchLen - 1 - _k]) { _k++; } else { break; } } if (_k == _nCurMayMaxMatchLen) { _bSuccess = true; } else { _bSuccess = false; } if (_bSuccess) { _nCurMaxMatchLen = _nCurMayMaxMatchLen; break; } } } else { if (arrSource_[_i] == arrPattern_[_nPreMaxMatchLen]) { _nCurMaxMatchLen = _nPreMaxMatchLen + 1; } else { for (int _nCurMayMaxMatchLen = _nPreMaxMatchLen; _nCurMayMaxMatchLen >= 0; _nCurMayMaxMatchLen--) { bool _bSuccess = true; int _k = 0; while (_k < _nCurMayMaxMatchLen) { if (arrSource_[_i - _k] == arrPattern_[_nCurMayMaxMatchLen - 1 - _k]) { _k++; } else { break; } } if (_k == _nCurMayMaxMatchLen) { _bSuccess = true; } else { _bSuccess = false; } if (_bSuccess) { _nCurMaxMatchLen = _nCurMayMaxMatchLen; break; } } } } if (_nCurMaxMatchLen == _nPatternLen) { _arrRet.Add(_i - _nPatternLen + 1); } _nPreMaxMatchLen = _nCurMaxMatchLen; }}

算法目标&正确性证明

算法正确性证明：算法以迭代方式实现以迭代方式实现的算法正确性证明依赖于循环不变式循环不变式：每次迭代开始时，我们总是可以得到到上次迭代位置为止，可以与模式产生的最大匹配的长度若循环不变式成立，可知，我们在每次迭代结束，得到本次迭代位置为止，可以与模式产生的最大匹配的长度若该长度 等于 模式本身长度，则 得到的一次模式的匹配。如此，必可得到 所有关于模式的匹配信息。得证。循环不变式证明：初始时，在首次迭代前，_nPreMaxMatchLen = 0，循环不变式成立。对于第k次迭代，依据循环不变式，_nPreMaxMatchLen表示到上次位置为止可以与模式产生的最大匹配的长度若本位置元素 等于 模式第(_nPreMaxMatchLen+1)处元素易于知道，此时从当前位置往前共(_nPreMaxMatchLen+1)个元素，分别依次与模式第(_nPreMaxMatchLen+1)到第一个元素依次相等。故，当前位置位置 可与模式达成的最大匹配长度必然 >= (_nPreMaxMatchLen+1)假设 当前位置位置 可与模式达成的最大匹配长度 为len > (_nPreMaxMatchLen+1)则，可推导出 当前上一位置为止 可与模式达成的最大匹配长度 必然 >= (len-1) > _nPreMaxMatchLen这与事实矛盾，故当前位置位置 可与模式达成的最大匹配长度为 (_nPreMaxMatchLen+1)若本位置元素 不等于 模式第(_nPreMaxMatchLen+1)处元素假设当前位置位置 可与模式达成的最大匹配长度 为len > (_nPreMaxMatchLen+1)则，可推导出 当前上一位置为止 可与模式达成的最大匹配长度 必然 >= (len-1) > _nPreMaxMatchLen这与事实矛盾，故当前位置位置 可与模式达成的最大匹配长度不会大于 (_nPreMaxMatchLen+1)假设当前位置位置 可与模式达成的最大匹配长度 为len = (_nPreMaxMatchLen+1)则，可推导出 本位置元素 等于 模式第(_nPreMaxMatchLen+1)处元素，这与事实矛盾，故当前位置位置 可与模式达成的最大匹配长度不会等于 (_nPreMaxMatchLen+1)综合，当前位置位置 可与模式达成的最大匹配长度只会<= (_nPreMaxMatchLen)而我们对_nPreMaxMatchLen,...,0可能的匹配长度依次进行考察故，考察完毕必可得到正确的_nCurMaxMatchLen综合，一次迭代结束，我们总是能得到 当前位置为止可能与模式产生的最大匹配的长度，进而，循环不变式成立。

转载地址：http://lxmgz.baihongyu.com/

你可能感兴趣的文章