Knuth-Morris-Pratt substring search

No algorithm description given

The basic idea behind the algorithm  discovered by Knuth, Morris, and Pratt is this: whenever we detect a mismatch, we  already know some of the characters in the text (since they matched the pattern characters prior to the mismatch). We can take advantage of this information to avoid backing  up the text pointer over all those known characters.   As a specific example, suppose that we have a two-character alphabet and are searching for the pattern B A A A A A A A A A . Now, suppose that we match five characters in the pattern, with a mismatch on the sixth. When the mismatch is detected, we know that the six previous  characters in the text must  be B A A A A B (the first  five match and the sixth does  not), with the text pointer now pointing at the B at the  end. The key observation is  that we need not back up the  text pointer i , since the previous four characters in the text  are all A s and do not match  the first character in the pattern. Furthermore, the character currently pointed to by  i is a B and does match the first character in the pattern, so we can increment i and  compare the next character in the text with the second character in the pattern. This  argument leads to the observation that, for this pattern, we can change the else clause  in the alternate brute-force implementation to just set j = 1 (and not decrement i ).  Since the value of i does not change within the loop, this method does at most N character compares. The practical effect of this particular change is limited to this particular  pattern, but the idea is worth thinking about—the Knuth-Morris-Pratt algorithm is a  generalization of it. Surprisingly, it is always possible to find a value to set the j pointer  to on a mismatch, so that the i pointer is never decremented. 


Tags
(no tags)

Cost Breakdown

0 cr
royalty per call
1 cr
usage per second
avg duration

Cost Calculator

API call duration (sec)
×
API calls
=
Estimated cost
per calls
for large volume discounts
For additional details on how pricing works, see Algorithmia pricing.

No permissions required

This algorithm does not require any special permissions.


To understand more about how algorithm permissions work, see the permissions documentation.

1. Type your input

2. See the result

Running algorithm...

3. Use this algorithm

curl -X POST -d '{{input | formatInput:"curl"}}' -H 'Content-Type: application/json' -H 'Authorization: Simple YOUR_API_KEY' https://api.algorithmia.com/v1/algo/reevu/KnuthMorrisPrattsubstringsearch/0.1.0
View cURL Docs
algo auth
# Enter API Key: YOUR_API_KEY
algo run algo://reevu/KnuthMorrisPrattsubstringsearch/0.1.0 -d '{{input | formatInput:"cli"}}'
View CLI Docs
import com.algorithmia.*;
import com.algorithmia.algo.*;

String input = "{{input | formatInput:"java"}}";
AlgorithmiaClient client = Algorithmia.client("YOUR_API_KEY");
Algorithm algo = client.algo("algo://reevu/KnuthMorrisPrattsubstringsearch/0.1.0");
AlgoResponse result = algo.pipeJson(input);
System.out.println(result.asJsonString());
View Java Docs
import com.algorithmia._
import com.algorithmia.algo._

val input = {{input | formatInput:"scala"}}
val client = Algorithmia.client("YOUR_API_KEY")
val algo = client.algo("algo://reevu/KnuthMorrisPrattsubstringsearch/0.1.0")
val result = algo.pipeJson(input)
System.out.println(result.asJsonString)
View Scala Docs
var input = {{input | formatInput:"javascript"}};
Algorithmia.client("YOUR_API_KEY")
           .algo("algo://reevu/KnuthMorrisPrattsubstringsearch/0.1.0")
           .pipe(input)
           .then(function(output) {
             console.log(output);
           });
View Javascript Docs
var input = {{input | formatInput:"javascript"}};
Algorithmia.client("YOUR_API_KEY")
           .algo("algo://reevu/KnuthMorrisPrattsubstringsearch/0.1.0")
           .pipe(input)
           .then(function(response) {
             console.log(response.get());
           });
View NodeJS Docs
import Algorithmia

input = {{input | formatInput:"python"}}
client = Algorithmia.client('YOUR_API_KEY')
algo = client.algo('reevu/KnuthMorrisPrattsubstringsearch/0.1.0')
print algo.pipe(input)
View Python Docs
library(algorithmia)

input <- {{input | formatInput:"r"}}
client <- getAlgorithmiaClient("YOUR_API_KEY")
algo <- client$algo("reevu/KnuthMorrisPrattsubstringsearch/0.1.0")
result <- algo$pipe(input)$result
print(result)
View R Docs
require 'algorithmia'

input = {{input | formatInput:"ruby"}}
client = Algorithmia.client('YOUR_API_KEY')
algo = client.algo('reevu/KnuthMorrisPrattsubstringsearch/0.1.0')
puts algo.pipe(input).result
View Ruby Docs
use algorithmia::*;

let input = {{input | formatInput:"rust"}};
let client = Algorithmia::client("YOUR_API_KEY");
let algo = client.algo('reevu/KnuthMorrisPrattsubstringsearch/0.1.0');
let response = algo.pipe(input);
View Rust Docs
Discussion
  • {{comment.username}}