
The Rabin-Karp algorithm, also known as the Karp-Rabin algorithm, was introduced by _Richard M. Karp_ and _Michael O. Rabin_ in 1987. It is designed to address the multiple pattern string matching problem.

Its implementation is somewhat unconventional. It begins by computing the hash values of two strings and then determines whether there is a match by comparing these hash values.

## Algorithm Analysis and Implementation

Choosing an appropriate hash function is crucial. Assuming the text string is $t[0, n)$, and the pattern string is $p[0, m)$, where $0<m<n$, let $Hash(t[i,j])$ represent the hash value of the substring $t[i, j]$.

When $Hash(t[0, m-1])!=Hash(p[0,m-1])$, it is natural to compare $Hash(t[1, m])$. In this process, if we recalculate the hash value for the substring $t[1, m]$, it would require $O(n)$ time complexity, which is not cost-effective. Observing that there are m-1 overlapping characters between the substrings $t[0, m-1]$ and $t[1, m]$, we can use a rolling hash function. This reduces the time complexity of recalculation to $O(1)$.

The rolling hash function used in the Rabin-Karp algorithm primarily leverages the concept of [Rabin fingerprint](https://en.wikipedia.org/wiki/Rabin_fingerprint). For example, the formula to calculate the hash value of the substring $t[0, m-1]$ is as follows:

$$
Hash(t[0, m-1])=t[0]*b^{m-1}+t[1]*b^{m-2}+...+t[m-1]*b^0
\\
\tag{t[0] represents the ASCII code of the character}
$$

Here, $b$ is a constant. In Rabin-Karp, it is generally set to 256 because the maximum value of a character does not exceed 255. The formula above has an issue - hash values could overflow. To address this, we take the modulus, and the value should be as large as possible and preferably a prime number. Here, we take 101.

The formula to calculate the hash value of the substring $t[1, m]$ is then:

$$
Hash(t[1,m])=(Hash(t[0,m-1])-t[0]*b^{m-1})*b+t[m]*b^0\\\tag{Please compare with the previous formula}
$$

The complete code is as follows:

```cpp
#include <iostream>
#include <string.h>

using namespace std;

#define BASE 256
#define MODULUS 101

void RabinKarp(char t[], char p[])
{
    int t_len = strlen(t);
    int p_len = strlen(p);

    // For rolling hash
    int h = 1;
    for (int i = 0; i < p_len - 1; i++)
        h = (h * BASE) % MODULUS;

    int t_hash = 0;
    int p_hash = 0;
    for (int i = 0; i < p_len; i++)
    {
        t_hash = (BASE * t_hash + t[i]) % MODULUS;
        p_hash = (BASE * p_hash + p[i]) % MODULUS;
    }

    int i = 0;
    while (i <= t_len - p_len)
    {
        // Considering the possibility of hash collisions, we use memcmp for additional verification
        if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0)
            cout << p << " is found at index " << i << endl;

        // Rolling hash
        t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS;

        // Avoiding negative values
        if (t_hash < 0)
            t_hash = t_hash + MODULUS;

        i++;
    }
}

int main()
{
    char t[100] = "It is a test, but not just a test";
    char p[10] = "test";

    RabinKarp(t, p);

    return 0;
}
```

The output is as follows:

```text
test is found at index 8
test is found at index 29
```

## Complexity Analysis

Let's examine the space complexity first, which is easily determined: $S(n)=O(1)$.

Now, consider the time complexity. Let the length of the text string be n and the pattern string be m. Preprocessing requires $O(m)$, and during matching, in the best case where there are no hash collisions, $T_{best}(n)=O(n-m)$. In the worst case, where there is a collision every time, $T_{worst}(n)=O((n-m)*m)$. In practical scenarios, n is often much larger than m, so the final complexity table is:

| $S_{n}$        | $O(1)$  |
| -------------- | ------- |
| $T_{best}(n)$  | $O(n)$  |
| $T_{worst}(n)$ | $O(mn)$ |

## Application Analysis

The primary application of the Rabin-Karp algorithm is in plagiarism detection for articles, such as the detection system used by [Semantic Scholar](https://www.semanticscholar.org/).

However, from the complexity data above, the Rabin-Karp algorithm does not seem to have a significant advantage. Is it practical for detecting text plagiarism? Feedback from actual usage results indicates that the time complexity for plagiarism detection is only $O(n)$. I believe this is mainly due to the following two points:

1. In real-life articles, the text data does not often exhibit as many hash collisions as we might imagine.
2. The original content in a submitted article is likely to be much larger than the plagiarized content. In other words, successful matches do not occur as frequently as we might imagine.

## References

- [Rabin–Karp algorithm](https://en.wikipedia.org/wiki/Rabin–Karp_algorithm)
- [Searching for Patterns | Set 3 (Rabin-Karp Algorithm)](https://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/)
- [Computer Algorithms: Rabin-Karp String Searching](http://www.stoimen.com/blog/2012/04/02/computer-algorithms-rabin-karp-string-searching/)


It is designed to address the multiple pattern string matching problem.

Rabin-Karp Algorithm


## Problem Description

The Josephus problem is a classic mathematical problem that describes the following scenario:

There are $n$ people standing in a circle. Starting from a certain person, they count off in sequence, and every $m$-th person steps out of the circle. The counting and elimination process continues, looping back to the next person when the end of the circle is reached. This continues until only one person remains. The problem is to determine the initial position of the last person remaining in the circle.

For example, when $n=7$ and $m=3$, the order of elimination is: $3, 6, 2, 7, 5, 1$. The last person remaining is at position $4$.

## Solution

The Josephus problem can be solved using either recursion or mathematical formulas. The recursive solution assumes knowledge of the solution for $n-1$ people, denoted as $f(n-1, m)$, and then calculates the solution for $n$ people using the formula:

$
f(n, m) = (f(n-1, m) + m) \% n
$

Here, $\%$ denotes the modulo operation. The base case is $f(1, m) = 0$, representing the solution when there is only one person.

The mathematical formula solution is derived based on the recurrence relation, resulting in the same formula:

$
f(n, m) = (f(n-1, m) + m) \% n
$

## Programming Implementation

When it comes to solving the Josephus problem, dynamic programming is an effective approach. Here is an example C code implementing dynamic programming to solve the Josephus problem:

```c
#include <stdio.h>

int josephus(int n, int m) {
    int dp[n + 1];
    dp[1] = 0; // Initial position when there is only one person

    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + m) % i;
    }

    return dp[n];
}

int main() {
    int n = 7; // Total number of people
    int m = 3; // Count off to m for elimination

    int lastPerson = josephus(n, m);
    printf("The last person remaining is: %d\n", lastPerson + 1); // Adding 1 due to 0-based indexing

    return 0;
}
```

In the above code, we use a dynamic programming array `dp` to store the next position after each person is eliminated. Through iteration, we can find the initial position of the last person remaining in the circle. In the `main` function, we set the total number of people `n` and the count to `m` for elimination. Then, we call the `josephus` function to calculate the position of the last person remaining and print the result.

Note that we assume people's positions start from 1, while array indices start from 0. Therefore, when printing the position of the last person remaining, we need to add 1.

Using dynamic programming provides an efficient solution to the Josephus problem, avoiding the repetitive calculations of recursion and improving code performance.


A description, analysis and solution for joseph circle problem.

Joseph Circle Problem


## Problem Description

This article presents an algorithm for the problem of selecting combinations of elements $C(n, m)$.

> Given a set $\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$ of size $n$ where $n>0$, extract $m$ elements $(0<m\leq n)$ as a combination and output all possible combination schemes.

## Model Establishment

According to the combination formula, the number of ways to select $n$ elements from a set of $m$ elements is given by $\left( \begin{array}{c} 	n\\ 	m\\ \end{array} \right) =\frac{P_{n}^{m}}{P_m}=\frac{n!}{m!\left( n-m \right) !}$.

For a set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, an auxiliary marking sequence $A=\left[ 1,1,1,...,0,0,0 \right]$ is established to indicate whether the corresponding elements are included in the combination: $A[i]=1$ indicates that element $a_{i}$ is included in the combination, where $A[i]=0$ indicates that element $a_{i}$ is not included in the combination.

**For example**, for the set $S=\left\{ a_{1},a_{2},a_{3},a_{4} \right\}$ and the combination $C(4,2)$, all possible combinations are $\left\{ a_{1},a_{2} \right\}$, $\left\{ a_{1},a_{3} \right\}$, $\left\{ a_{1},a_{4} \right\}$, $\left\{ a_{2},a_{3} \right\}$, $\left\{ a_{2},a_{4} \right\}$, $\left\{ a_{3},a_{4} \right\}$. The corresponding auxiliary marking sequences are $\left\{ a_{1},a_{2} \right\}\rightarrow\left[ 1,1,0,0 \right]$, $\left\{ a_{1},a_{3} \right\}\rightarrow\left[ 1,0,1,0 \right]$, $\left\{ a_{1},a_{4} \right\}\rightarrow\left[ 1,0,0,1 \right]$, $\left\{ a_{2},a_{3} \right\}\rightarrow\left[ 0,1,1,0 \right]$, $\left\{ a_{2},a_{4} \right\}\rightarrow\left[ 0,1,0,1 \right]$, $\left\{ a_{3},a_{4} \right\}\rightarrow\left[ 0,0,1,1 \right]$.

The content expressed by the auxiliary marking sequence is the elements corresponding to the items marked as $1$ in the sequence, selected in the set and included in the combination. This auxiliary sequence facilitates the computation of combinations.

## Auxiliary Sequence Transformation

The concept of the auxiliary marking sequence has been introduced above. Now, two special auxiliary marking sequences are defined.

**Definition** $A(S)$ represents the **initial state auxiliary marking sequence** for the combination problem of selecting $C(n, m)$ elements from the set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, denoted as $A(S)=\left[ a_{1},a_{2},...,a_{n},a_{n+1},a_{n+2},...,a_{m} \right]$, where $a_{i}=1(0<i\leq n)$ and $a_{j}=0(n+1 \leq j\leq m)$. It can be considered as the first combination method among all combination methods for the combination problem.

> **Example** The sequence $A=[1,1,1,1,0,0,0,0,0]$ is the initial state.

The initial state auxiliary marking sequence has been introduced above. Now, the **terminal state auxiliary marking sequence** is introduced.

**Definition** For the combination problem of selecting $C(n, m)$ elements from the set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, the auxiliary marking sequence $A=[a_{1},a_{2},...,a_{n-m},...,a_{m}]$ is defined, where $a_{i}=0(0<i\leq n-m)$ and $a_{j}=1(n-m<j\leq m)$. This sequence is called the **terminal state auxiliary marking sequence** of this set.

> **Example** The sequence $A=[0,0,0,0,1,1,1,1,1]$ is the terminal state.

**Definition** The operation function $Countf(A,i)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as the number of elements satisfying $a_{j}=1(0<j< i)$ in the subsequence $A=\left[ a_{1},a_{2},...,a_{i} \right]$.

> **Example** If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Countf(A,i)$ for $i=7$. Since before $A[7]$ (excluding $A[7]$), there are a total of $3$ elements $1$ at $A[1]$, $A[4]$, and $A[6]$, so the value of $Countf(A,i)$ for $i=7$ is $3$.

**Definition** The operation function $Exch(A)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as follows: find the smallest index $i$ satisfying $a_{i}=1$ and $a_{i+1}=0$, where $0<i\leq m-1$. Then exchange their values, i.e., set $a_{i}=0$ and $a_{i+1}=1$, obtaining the new sequence $A'$.

> **Example** If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Exch(A)$. Obviously, find the minimum $i=1$, and get $a_{1}=1,a_{2}=0$. Swap them to get the new sequence $A'=Exch(A)=\left[ 0,1,0,1,0,1,1,1 \right]$

**Definition** The operation function $Movb(A,i)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as follows: let $p=Countf(A,i)$ and $q=i-p-1$. Transform $A$ to get the new sequence $A'=[a_{1},a_{2},...,a_{p},a_{p+1},...,a_{i-1},a_{i},...,a_{m}]$, where $a_{i}=1(1<i\leq p)$ and $a_{j}=0(p<j<i)$.

> **Example** If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Movb(A,i)$ for $i=5$. The new sequence is $A'=Movb(A,5)=\left[ 1,1,0,0,0,1,1,1 \right]$.

**Definition** Based on the auxiliary marking sequence $A$, output a combination scheme for the set $S$, called a restoration for sequence $A$. Denoted as $C(A)=\left\{ a_{i}\in S|A[i]=1 ,0<i\leq m \right\}$.

> **Example** For the set $S=\left\{ a_{1},a_{2},a_{3},a_{4},a_{5},a_{6} \right\}$ and the sequence $A=[1,1,0,0,1,0]$, a restoration for $S$ with respect to $A$ is $\left\{ a_{1},a_{2},a_{5} \right\}$.

## Algorithm Method

- Step 1: Obtain $A=A(S)$ from the set $S$, i.e., the initial state auxiliary marking sequence.
- Step 2: Output $C(A)$.
- Step 3: Check if the obtained auxiliary marking sequence is in the terminal state. If yes, terminate. If no, proceed to the next step.
- Step 4: Perform the transformation $A=Exch(Movb(A))$, and go back to Step 2.

With the above method, all combination schemes for the combination problem of selecting $C(n,m)$ elements from the set $S$ can be output.


This article presents an algorithm for the problem of selecting combinations of elements.

Problem: Element Combination Using Marking Method


Wilson Score sorting algorithm, Wilson Score, is used for quality sorting. The data contains positive and negative reviews. Taking into account the **number of comments** and **praise rate**, the higher the score, the higher the quality.

$$
n = u + v \\
p = \frac{u}{v} \\
S = \frac{(p + \frac{z_{α}^{2}}{2n} - \frac{z_{α}^{2}}{2n}\sqrt{4n(1-p)p+z_{α}^{2}} )}{(1+\frac{z_{α}^{2}}{n})}
$$

$u$ represents the number of positive examples (good reviews), $v$ represents the number of negative examples (bad reviews), $n$ represents the total number of instances (total number of reviews), $p$ represents the positive rate, and $z$ is the score of the normal distribution. Number of bits (parameter), $S$ represents the final Wilson score. $z$ generally takes a value of 2, which is 95% confidence.

Here is the quantile table for the normal distribution:
![](https://upload-images.jianshu.io/upload_images/749674-35a2dc9beddd2083.png?imageMogr2/auto-orient/strip|imageView2/2/w/456/format/webp)

**Algorithm traits:**

1. Properties: The range of score $S$ is $[0,1)$, effect: normalized, suitable for sorting
2. Properties: When the number of positive examples $u$ is $0$, $p$ is $0$, and the score $S$ is $0$; effect: no positive comments, the score is the lowest;
3. Properties: When the number of negative examples $v$ is $0$, $p$ is $1$, degenerates to $1/(1 + z^2 / n)$, and the score $S$ is always less than $1$; effect: the score has permanent comparability;
4. Properties: When $p$ remains unchanged, the larger $n$ is, the reduction speed of the numerator is smaller than the reduction speed of the denominator, and the greater the score $S$, and vice versa; Effect: The positive rate $p$ is the same, the total number of instances is $n The more $, the more $S$ you score;
5. Properties: When $n$ tends to infinity, it degenerates to $p$, and the score $S$ is determined by $p$; Effect: When the total number of comments $n$ is more, the positive rate $p$ will bring the score $S The improvement of $ is more obvious;
6. Properties: When the quantile $z$ is larger, the total number of reviews $n$ is more important, and the praise rate $p$ is less important, and vice versa; Effect: The larger $z$ is, the total number of reviews $n$ is more important. The degree of discrimination is low; the smaller $z$ is, the more important the praise rate $p$ is;

[Click here to get source code](https://github.com/SpikeKing/MachineLearningTutorial/tree/master/wilson_score)

Python Implementation.

```python
def wilson_score(pos, total, p_z=2.):
    pos_rat = pos * 1. / total * 1.  # 正例比率
    score = (pos_rat + (np.square(p_z) / (2. * total))
             - ((p_z / (2. * total)) * np.sqrt(4. * total * (1. - pos_rat) * pos_rat + np.square(p_z)))) / \
            (1. + np.square(p_z) / total)
    return score
```

Distribution plot of Wilson score algorithm

![](https://upload-images.jianshu.io/upload_images/749674-3340e75c9438e31e.png?imageMogr2/auto-orient/strip|imageView2/2/w/1200/format/webp)

Let's try to put this theory into use with following example.

**Example:** Suppose Doctor A has 100 reviews, 1 negative review and 99 positive reviews. Doctor B has 2 reviews, both of which are good reviews. Which one should be ranked first?

When $z=2$, that is, 95% confidence level, doctor A's score is 0.9440, doctor B's score is 0.3333, and doctor A ranks in front.

---

PS: **Rating Level** Question: What should we do if we have a five-star evaluation system or a hundred percent evaluation system?

Just change the Wilson score formula from **Bernoulli distribution** to **normal distribution**.

$$
S = \frac{(μ + \frac{z_{α}^{2}}{2n} - \frac{z_{α}^{2}}{2n}\sqrt{4nσ^{2}+z_{α}^{2}} )}{(1+\frac{z_{α}^{2}}{n})} \\
μ ∈(0,1)
$$

**Note**: The mean and variance are both normalized values.

Python Implementation.

```python
def wilson_score_norm(mean, var, total, p_z=2.):
    # The mean variance needs to be normalized to fit the quantiles of the normal distribution
    score = (mean + (np.square(p_z) / (2. * total))
             - ((p_z / (2. * total)) * np.sqrt(4. * total * var + np.square(p_z)))) / \
            (1 + np.square(p_z) / total)
    return score
```

Example of normalization:

```python
def test_of_values():
    max = 5.  # Maximum evaluation value.
    min = 1.  # Minimum evaluation value.
    values = np.array([1., 2., 3., 4., 5.])  # Example

    norm_values = (values - min) / (max - min)  # Normalize
    total = norm_values.size
    mean = np.mean(norm_values)
    var = np.var(norm_values)
    return total, mean, var
```

---

PS: About the **z parameter**, that is, the normal quantile. The normal quantile affects the distribution of Wilson scores, and the value of the $z$ parameter is based on the magnitude of the number of samples. For example: the same 100 samples, 90 positive reviews, $z$ value is 2 or 6, the scores are very different, and the number of samples accommodated (or distinguished) by the system is also very different (the same is 0.82 points and 90% positive reviews, $z=2$ requires 100 samples, $z=6$ requires 1000 samples), **generally speaking, the larger the magnitude of the number of samples, the larger the value of z.**

```python
print 'score: %s' % wilson_score(90, 90 + 10, p_z=2.)
print 'score: %s' % wilson_score(90, 90 + 10, p_z=6.)
print 'score: %s' % wilson_score(900, 900 + 100, p_z=6.)

# take 2-100：score: 0.823802352689
# take 6-100：score: 0.606942322627
# take 6-1000：score: 0.828475631056
```

References:

- [Binomial proportion confidence interval](https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval)
- [Normal distribution](https://en.wikipedia.org/wiki/Normal_distribution)
- [How Not To Sort By Average Rating](http://www.evanmiller.org/how-not-to-sort-by-average-rating.html)
- [Relationship between Binomial and Normal Distributions](http://www.real-statistics.com/binomial-and-related-distributions/relationship-binomial-and-normal-distributions/)
- [Relevant Source Code](https://github.com/SpikeKing/MachineLearningTutorial/blob/master/wilson_score/wilson_score_model.py)


MY BLOG

ALGORITHM

Rabin-Karp Algorithm

Joseph Circle Problem

Problem: Element Combination Using Marking Method

The Wilson Score - Ranking Algorithm