mockers
Would you like to react to this message? Create an account in a few clicks or log in to continue.
mockers

here is place to discuss interesting mathematical / computer science problems


SUB-STRING Matching

mockers :: Algorithms

Go down

SUB-STRING Matching Empty SUB-STRING Matching

Post  ramthegreatcv Tue Feb 24, 2009 10:19 pm

Naive string matching:

for (i=0; T[i] != '\0'; i++)
{
for (j=0; T[i+j] != '\0' && P[j] != '\0' && T[i+j]==P[j]; j++) ;
if (P[j] == '\0') found a match
}

for more details:
http://www.ics.uci.edu/~eppstein/161/960227.html
ramthegreatcv
ramthegreatcv

Posts : 55
Join date : 2009-01-30
Age : 36

Back to top Go down

SUB-STRING Matching Empty Knuth Morris Pratt

Post  ramthegreatcv Sat Aug 08, 2009 7:53 pm

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Code:

#include<iostream>
#include<string>
//knuth morris pratt

using namespace std;

int Table[100];

void tableFilling(char* W){
    Table[0] = -1;
    Table[1] = 0;
   
    int pos = 2;
    int cnd =0;
   
    while(pos < strlen(W)){
        if(W[pos -1 ] == W[cnd]){
            Table[pos] = cnd+1;
            cnd++ ;
            pos++ ;     
        }   
        else if(cnd > 0){
            cnd = Table[cnd];
        } 
        else{
            Table[pos] = 0;
            pos++ ;
        }
    } 
}

int KNP(char* W,char*T){
    int m=0,i=0;
    while(m+i < strlen(T)){
        cout<<"m+i ";
        cout.width(2);
        cout<<m+i<<":"<<T[m+i]<<" ";
        cout<<"i";
        cout.width(2);
        cout<<i<<W[i]<<endl;
        if(W[i] == T[m+i]){
          i++;
          if(i == strlen(W))
              return m;
              }
        else{
            m = m+i-Table[i];
            if(i>0){
                i=Table[i];
            }
        }
    }
    return strlen(T);
}

void printTable(char*W,char* T){
    cout<<"T:    ";
    for(int i=0;i<strlen(T);i++){
          cout.width(2);
          cout<<T[i];       
    }
    cout<<"\nW:    ";
    for(int i=0;i<strlen(W);i++){
          cout.width(2);
          cout<<W[i];       
    }
    cout<<"\nTable: ";
    for(int i=0;i<strlen(W);i++){
          cout.width(2);
          cout<<Table[i];       
    }
    cout<<"\n";
}

int main(){
    char W[100]="abcabcddabcabc",T[100]="abcabcabcddabcabc";
    //cout<<"search for ";
    //cin>>W;
    //cout<<" in ";
    //cin>>T;
    tableFilling(W);
    printTable(W,T);
    cout<<"substring found at:"<<KNP(W,T)<<endl;
   
    int n;
    cin>>n;
}
ramthegreatcv
ramthegreatcv

Posts : 55
Join date : 2009-01-30
Age : 36

Back to top Go down

Back to top

mockers :: Algorithms

 
Permissions in this forum:
You cannot reply to topics in this forum