Knuth Morris Pratt

 avatar
unknown
c_cpp
3 years ago
346 B
2
Indexable
int KMP(string T,string P){
  int _left = 0 , _right , cnt = 0 ;
  for( _right = 0 ; _right < T.size() ; _right ++ ){
    while( _left > 0 && P[_left] != T[_right] ) _left = _next[_left-1] ;
    if( P[_left] == T[_right] )_left ++ ;
    if( _left == P.size() ) {
      cnt ++ ;
      _left = _next[_left-1] ;
    }
  }
  return cnt ;
}