KMP Algorithm Implementation in C++ gives Runtime Error -
i have implemented knuth-morris-pratt algorithm in c++ . implementation seems right encountering runtime error cant seem figure out . need in .
#include <iostream> #include <cstring> #include <string> using namespace std; int* prefixfunction(string pattern) { int m = pattern.length() ; int prefixtable[m] ; prefixtable[0] = 0 ; int k = 0 ; for(int q = 1; q<m; q++) { while(k>0&&pattern[k]!=pattern[q]) { k = prefixtable[k] ; } if(pattern[k]==pattern[q]){ k = k + 1 ; } prefixtable[q] = k ; } return prefixtable ; } void kmp(string text,string pattern) { int* prefixtable = prefixfunction(pattern) ; int n = text.length() ; int m = pattern.length() ; int q = 0 ; //characters matched for(int i=0;i<n;i++) { while(q>0&&pattern[q]!=text[i]) { q = prefixtable[q] ; } if(pattern[q]==text[i]) { q = q + 1 ; } if(q==m) { cout<<"found : "<<i-m ; q = prefixtable[q] ; } } } int main() { string text, pattern ; cout<<"enter text : " ; cin>>text ; cout<<"enter pattern : " ; cin>>pattern ; kmp(text,pattern) ; return 0 ; } i runtime error after program asks input . guidance needed .
prefixfunction returning pointer local variable, prefixtable, automatic storage.
when function returns, array ceases exist, , dereferencing pointer makes program undefined.
(what's happening in case calls length() put own automatic variables array used be, , when use "values" indexes program goes boom.)
consider using std::vector<int> instead of array.
std::vector<int> prefixfunction(string pattern) { int m = pattern.length(); std::vector<int> prefixtable(m); // before... if can't use std::vector, use dynamic allocation (remember free memory afterwards), or pass table function parameter instead of returning it:
void prefixfunction(string pattern, int* prefixtable) // ... void kmp(string text,string pattern) { int m = pattern.length(); int prefixtable[m]; prefixfunction(pattern, prefixtable); // ... 
Comments
Post a Comment