0001 constexpr int M = 97; //97便于对照实例来验证算法；只要更新指纹时不致逸出，就可以且应该取更大的M
0002 constexpr int R = 10; //以不含'0'的十进制数字串为例，与M同样，在实际中需扩充至更一般的字符串
0003 auto DIGIT = [](char* S, int i) { return S[i] - '0'; }; //十进制数字串S中第i位的数值
0004 
0005 int match(char* T, int n, char* P, int m) { //Karp-Rabin算法：m <= n
0006    int S = 1; //S = R^(m-1) % M：最高位对指纹的贡献，提前算出备用
0007    for (int j = 1; j < m; j++) //O(m)：直接调用power(R,m-1)通常都会溢出
0008       S = (R*S) % M;
0009 
0010    int hashP = 0, hashT = 0; //[初始化]
0011    for (int j = 0; j < m; j++) { //[O(m)时间] 算出P[0,m)与T[0,m)的指纹
0012       hashP = (hashP*R + P[j]-'0') % M;
0013       hashT = (hashT*R + T[j]-'0') % M;
0014    }
0015 
0016    for (int i = 0; ; i++) { //[查找匹配，期望O(n)时间] 逐个尝试每个对齐位置i
0017       if (hashT == hashP) //若指纹相等（概率约1/M，完全可控），则需蛮力地比对O(m)个字符
0018          for (int j = 0, k = i; (j < m) && (P[j] == T[k]); j++, k++) //以确认
0019             if (j == m-1) return i; //匹配
0020       if (i == n-m) return i+1; //失配
0021       hashT = (hashT + (M - DIGIT(T, i))*S) % M; //[指纹更新] 从原指纹之中排除T[i]的贡献
0022       hashT = (hashT*R + DIGIT(T, i+m)) % M; //[O(1)时间] 整体左移一位之后，加上T[i+m]的贡献
0023    } //for
0024 } //match