C++ Finite Automata algorithm for Pattern Searching

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; 
}