algorithm - Knuth-Morris-Pratt implementation in pure C -

-

i have next kmp-implementation:

#include <stdio.h> #include <stdlib.h> #include <string.h>  int kmp(char substr[], char str[]) {    int i, j, n, m;     n = strlen(str);    m = strlen(substr);     int *d = (int*)malloc(m * sizeof(int));    d[0] = 0;     for(i = 0, j = 0; < m; i++)    {       while(j > 0 && substr[j] != substr[i])       {          j = d[j - 1];       }        if(substr[j] == substr[i])       {          j++;          d[i] = j;       }    }     for(i = 0, j = 0; < n; i++)    {       while(j > 0 && substr[j] != str[i])       {          j = d[j - 1];       }        if(substr[j] == str[i])       {          j++;       }        if(j == m)       {          free(d);          return - j + 1;       }    }     free(d);     return -1; }  int main(void) {    char substr[] = "world",       str[] = "hello world!";     int pos = kmp(substr, str);     printf("position starts at: %i\r\n", pos);     return 0; }

you can test here: http://liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80

it works on small strings, , have tested large loop, on way fine.

but if change substring i'm searching , complete string these:

char substr[] = "%end%", str[] = "<h1>the result is: <%lua% oleg = { x = 0xa }          table.insert(oleg, y) oleg.y = 5 print(oleg.y) %end%></h1>";

only after first try, implementation fails...

please, me repairing implementation of kmp make algorithm work such data in strings...

in 1 place deviate source, source has

while(j>0 && p[j]!=p[i]) j = d[j-1];     if(p[j]==p[i])         j++;         d[i]=j;

while have

while(j > 0 && substr[j] != substr[i]) {     j = d[j - 1]; } if(substr[j] == substr[i]) {     j++;     d[i] = j; }

being deceived source's indentation. in source, there no braces around if() branch, increment j++; controlled if; d[i] = j; unconditional.

then, source has error, due unusual use of indices. correct way set array is

int *d = (int*)malloc(m * sizeof(int)); d[0] = 0;  for(i = 1, j = 0; < m; i++) {     while(j > 0 && substr[j-1] != substr[i-1])     {         j = d[j - 1];     }      if(substr[j] == substr[i])         j++;     d[i] = j; }

but it's confusing, since setup here uses indices i-1 , j-1 i , j determine d[i]. usual way implement different; way implemented in c#. since that's form find in sources, it's far easier convince of correctness of that.


Comments

Post a Comment

Popular posts from this blog

c# - SVN Error : "svnadmin: E205000: Too many arguments" -

-
i trying reposotries using c# code process svncommand = null; var psi = new processstartinfo("svnadmin"); psi.redirectstandardoutput = true; psi.redirectstandarderror = true; psi.useshellexecute = false; psi.arguments= @"dump c:\repositories\myrepo > c:\temp\myrepodumpfile.dump"; using (svncommand = process.start(psi)) { var myoutput = svncommand.standardoutput; var myerror = svncommand.standarderror; debug.write("output :" + environment.newline + environment.newline + myoutput.readtoend() + environment.newline + "error :" + environment.newline + environment.newline + myerror.readtoend()); svncommand.close(); } when use dump command commandline svnadmin dump c:\repositories\myrepo > c:\temp\myrepodumpfile.dump it works fine when try ...
Read more

c# - Copy ObservableCollection to another ObservableCollection -

-
how copy observablecollection item observablecollection without reference of first collection? here observablecollection item value changes affecting both collections. code private observablecollection<ratemodel> _allmetalrate = new observablecollection<ratemodel>(); private observablecollection<ratemodel> _metalrateondate = new observablecollection<ratemodel>(); public observablecollection<ratemodel> allmetalrate { { return this._allmetalrate; } set { this._allmetalrate = value; notifypropertychanged("metalrate"); } } public observablecollection<ratemodel> metalrateondate { { return this._metalrateondate; } set { this._metalrateondate = value; notifypropertychanged("metalrateondate"); } } foreach (var item in metalrateondate) allmetalrate.add(item); what causing , how can solve it? you need clone object referenced item before it's a...
Read more

All overlapping substrings matching a java regex -

-
is there api method returns (possibly overlapping) substrings match regular expression? for example, have text string: string t = 04/31 412-555-1235; , , have pattern: pattern p = new pattern("\\d\\d+"); matches strings of 2 or more characters. the matches are: 04, 31, 412, 555, 1235. how overlapping matches? i want code return: 04, 31, 41, 412, 12, 55, 555, 55, 12, 123, 1235, 23, 235, 35. theoretically should possible -- there obvious o(n^2) algorithm enumerates , checks substrings against pattern. edit rather enumerating substrings, safer use region(int start, int end) method in matcher . checking pattern against separate, extracted substring might change result of match (e.g. if there non-capturing group or word boundary check @ start/end of pattern). edit 2 actually, it's unclear whether region() expect zero-width matches. specification vague, , experiments yield disappointing results. for example: string line = "xx90xx"; strin...
Read more