Knuth Morris Pratt
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 ; }