C++ Knuth Morris Pratt Algorithm

Açıklama

• Knuth Morris Prat Algoritması mantığı metin içersinden kelime aramadan önce ön işlem gerektirmektedir.
• Ön işlem aranacak olan kelimenin metin içersinde bulunmaması durumunda kaç adım yol alacağıdır. Bu ön işlem sonucu değerler bir boyutlu bir matrise yazılır.

Kod

#include <bits/stdc++.h> 
#include <iostream>
#include<string.h> 
#include<string>
#include <sys/time.h>

// MEHMET ERIM KMP


using namespace std;
  

void computeLPS(string pattern,int lps[]) 
{ 

	int len = pattern.size();
  
    lps[0] = 0;
  
    int i = 0, j = 1;
    
    while (j < len) { 
        if (pattern[i] == pattern[j]) {  // if i and j is match value of i+1 and lps(j) write
        	i++;
        	lps[j] = i;
        	j++;  
        } 
        else                      
        { 
    
            if (i != 0) {               // if i is not at index of 0 go back
                i--;
  			}
            else                         // if i is beginning, put 0 to LPS
            { 
                lps[j] = 0; 
                j++; 	
            } 
        } 
    } 
    
} 


void KMPSearch(string text, string pattern) 
{ 


	int m = pattern.size();
    int n = text.size();

    int lps[m]; 
  
    computeLPS(pattern, lps); 
    
	
    int i = 0; 
    int j = 0; 
    
    
    while (i <= n) { 

    
    	if(j==m){
    		 printf("Pattern found at index %d \n", i-j); 
		}
    
    
    
        if (pattern[j] == text[i]) { 
            j++; 
            i++; 
        }else{
        	
	        	
	        if(j == 0){      // if i at first characters in the pattern, shift 1 steps
	        	
	        	i++;
	     
	        	
			}else{            // if i not at first character in the pattern, shift until lps values

			  	i+= (j)-lps[j-1];  

			}
		
		j = 0;  // if any missmatch j set default value of 0 
		
		}

	} 

}
  
int main() 
{ 

	string pattern = "AAA";
	string text = "AAAA";

	KMPSearch(text,pattern);
	
    return 0; 
}