text T a b c a a a b a b a S=3 pattern a a we say that pattern P occurs with shift s in text T (or,equivalently,that pattern P occurs beginning at position s+1 in text T)if 0≤s≤n-m and T5+l.s+m=P[l.m(that is,.ifT5+j】=P[Ujl,for 1jm).If P occurs with shift s in T,then we call s a valid shift;otherwise, we call s an invalid shift.The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T