Linked Lists - A Concise and Practical Introduction to Programming Algorithms in Java - page 167

test string";char [] T=stringt.toCharArray(); ). Deduce a naive
algorithm for reporting the potential occurences of M in T .Let m and t be
the respective length of arrays M and T . What is the time complexity of
this search procedure? Karp and Robin proposed an effective linear time
algorithm that consists of using a signature function S . The principle is
as follows: Compute once for all the signature of the motif pattern M ,and
get S ( M ). Then for all i , check whether the signature of T [ i..i + m

1]
matches the signature of M . If signatures do not match then there
is no occurrence at that position. Otherwise, when signatures match,
we still need to check whether it is a true occurence or not. Give
an implementation of the Karp-Rabin algorithm using as a signature
function the sum of the character ASCII codes of an array:

−

Program 7.20 An example of signature function for the Karp-Rabin
pattern matching algorithm
static long signature( char [] X, int m, int i)
long result=0;
for ( int j=i ; j < i+m; j ++)
result+=X[ j ];
return result ;
}