0001 int match ( char* P, char* T ) { //串匹配算法(Karp-Rabin) 0002 size_t m = strlen ( P ), n = strlen ( T ); //assert: m <= n 0003 HashCode Dm = prepareDm ( m ), hashP = 0, hashT = 0; 0004 for ( size_t i = 0; i < m; i++ ) { //初始化 0005 hashP = ( hashP * R + DIGIT ( P, i ) ) % M; //计算模式串对应的散列值 0006 hashT = ( hashT * R + DIGIT ( T, i ) ) % M; //计算文本串(前m位)的初始散列值 0007 } 0008 for ( size_t k = 0; ; ) { //查找 0009 if ( hashT == hashP ) 0010 if ( check1by1 ( P, T, k ) ) return k; 0011 if ( ++k > n - m ) return k; //assert: k > n - m,表示无匹配 0012 else updateHash ( hashT, T, m, k, Dm ); //否则,更新子串散列码,继续查找 0013 } 0014 }