# KMP-Example

Algorithm

This algorithm is a two step process.First we create a auxiliary array lps[] and then use this array for searching the pattern.

Preprocessing :

1. We pre-process the pattern and create an auxiliary array lps[] which is used to skip characters while matching.
2. Here lps[] indicates longest proper prefix which is also suffix.A proper prefix is prefix in which whole string is not
```included.For example, prefixes of string **ABC** are **“ ”**,
**“A”**, **“AB”** and **“ABC”**. Proper prefixes are **“ ”**, **“A”** and **“AB”**. Suffixes of the string are **“ ”**, **“C”**, **“BC”** and **“ABC”**.```

Searching

1. We keep matching characters txt[i] and pat[j] and keep incrementing i and j while pat[j] and txt[i] keep matching.
2. When we see a mismatch,we know that characters pat[0..j-1] match with txt[i-j+1…i-1].We also know that lps[j-1] is count of characters of pat[0…j-1] that are both proper prefix and suffix.From this we can conclude that we do not need to match these lps[j-1] characters with txt[i-j…i-1] because we know that these characters will match anyway.

Implementaion in Java

```public class KMP {

public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "abcabdabc";
String pattern = "abc";
KMP obj = new KMP();
System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
}

public int[] computeLPS(char[] str){
int lps[] = new int[str.length];

lps = 0;
int j = 0;
for(int i =1;i<str.length;i++){
if(str[j] == str[i]){
lps[i] = j+1;
j++;
i++;
}else{
if(j!=0){
j = lps[j-1];
}else{
lps[i] = j+1;
i++;
}
}

}

return lps;
}

public boolean patternExistKMP(char[] text,char[] pat){
int[] lps = computeLPS(pat);
int i=0,j=0;
while(i<text.length && j<pat.length){
if(text[i] == pat[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}

if(j==pat.length)
return true;
return false;
}

}```
{"ft_lang_label":"__label__en","ft_lang_prob":0.6147667,"math_prob":0.96433246,"size":1961,"snap":"2020-10-2020-16","text_gpt3_token_len":573,"char_repetition_ratio":0.10781809,"word_repetition_ratio":0.013422819,"special_character_ratio":0.32942376,"punctuation_ratio":0.15647922,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97147566,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-04-09T00:01:23Z\",\"WARC-Record-ID\":\"<urn:uuid:b6bbc4d5-be16-4e45-bc9d-6ff274c3d5fa>\",\"Content-Length\":\"13496\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:34457056-c6ce-49d4-a33c-a1bd7f708cec>\",\"WARC-Concurrent-To\":\"<urn:uuid:0b197b36-4f05-45d8-a57f-f089dfa53b57>\",\"WARC-IP-Address\":\"159.65.216.232\",\"WARC-Target-URI\":\"https://www.programming-books.io/essential/algorithms/kmp-example-5f9d16f1206249d0b9e62e687ddaa4e0\",\"WARC-Payload-Digest\":\"sha1:YEUXUA254JXHV7IHF3EMVHGYVZI4UURU\",\"WARC-Block-Digest\":\"sha1:DGZT33AKCYAUO77SFL223AM446WX7YPR\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585371826355.84_warc_CC-MAIN-20200408233313-20200409023813-00302.warc.gz\"}"}