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

  • Finite Automata kullanarak graflar üzerinden kelime arama işlemidir. (Finite Automata algorithm for Pattern Searching)
  • Eğer aranan kelime final state yani son bitiş düğümüne ulaştıysa kelime bulunmuştur, eğer final yerine başka düğümdeyse kelime bulunmamıştır.

 

 

Kod

#include<stdio.h> 
#include<string.h> 
#include<string>
#include <sys/time.h>
#include <iostream>
#define NO_OF_CHARS 256 


// MEHMET ERIM FSM


using namespace std;
  
void createTable(string pattern,string patternCharacter,int TF[][NO_OF_CHARS]){

//	string pattern = "abcabd";
	
//	string patternCharacter = "abcd";
	
	int size =pattern.size();
	
//	int TF[size+1][NO_OF_CHARS];
	
	
	for(int i=0;i<=size;i++){       // all variable of array is 0
		
		for(int j=0;j<NO_OF_CHARS;j++){
			TF[i][j] = 0;
		}
	}
	
		
	for(int i=0;i<=size;i++){     // main algorithm
		
		for(int j=0;j<NO_OF_CHARS;j++){
		
			if(j==(int)pattern[i]){     // in the pattern characters,it  put the index of indis
				TF[i][j] = i+1;
			}	
			else{
			
					
						string a = pattern.substr(0,i);                  // to obtain part of pattern so to compare similarity  ex ABCAB
						a+=(char)j;
						
						
						string a1= a.substr(0,a.size()-1);             // get left part of pattern             ex ABCA
						
						string a2 = a.substr(1,a.size());				// get right part of pattern           ex BCAB
						
				//		cout << a << endl;
						
				//		cout << a << " " << a1 << " " << a2 << endl;
						
						
						string c1=a1;                                 // to 
						string c2=a2;
				
							
							
					//	cout << "------------"<< endl;
							
						for(int m=0;m<a1.size();m++){         // this loops to reduce part to pattern
							
								
					
							
							
					//		cout << c1 << " " << c2 << endl;
							if(c1.compare(c2) == 0){        // if the right and left pattern is match, put the value at the index and exit from here;
					//			cout << "esit "<< i << " "<< j;
								TF[i][j] = c1.size();
								break;
								
							}
							
					
							c1 = a1.substr(0,a1.size()-m-1);          // to reduce left pattern
					 	 c2 = a2.substr(m+1,a2.size());	              // to reduce right pattern
								
						}

					
				}
				
				
			}
			
		
		}
	

}



void search(string pat, string txt,string patternCharacters) 
{ 
    int M = pat.size();
    int N = txt.size();
    
  
    int TF[M+1][NO_OF_CHARS]; 
  
    createTable(pat, patternCharacters, TF);  // create table for FSM
    

    int i, state=0; 
    
    for (i = 0; i < N; i++) 
    { 
        state = TF[state][txt[i]]; 
        if (state == M) 
  			 printf("Pattern found at index %d \n", i-M+1); 
                                       
    } 
} 
  

int main() 
{ 


    string pattern = "clear reflection";
    string patternCharacters = "clearfction";   // each letter of pattern
	string text = "AAAAAAAAAAAAAA";
	
  
   	search(pattern,text,patternCharacters);

	
	
    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.