Bilgilendirme : İçerik adresleri değişmiştir. Lütfen, aradığınız içeriği arama kutucuğundan arayınız =)

Aramak istediğiniz sözcüğü giriniz...

Java
Programlama
  • Java
  • Python
  • C++
  • C#
  • MATLAB
  • MIPS Assembly
  • PIC Assembly
Web Prog.
  • HTML
  • CSS
  • PHP
  • Javascript
Veritabanı Prog.
  • SQL
Arama Yap
İstediğin programlama dilinde sınıf, fonksiyon yada bir terimi arama alanına yaz.
Çıkan seçeneklere göz at
Seçenekler arasından senin işine yaradığı seçeneği seç.
İçeriğe göz at
Seçtiğin seçenekte yer alan örneğe bakarak bilgi edin ya da kullan.
MEHMET ERIM
2019-05-16

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; 
} 
İçeriği Paylaş
Facebook
Twitter
Google+
Linkedin
Yorumlar
Biz Kimiz ?
Java, Python, C++, C#, PHP, HTML, CSS, SQL ve MATLAB programlama dillerine ait sınıf ve fonksiyonların tanım ve açıklamalarını içeren bir websitesiyiz.
Günden güne içeriklerimizi yenileyip, arttırıyoruz.