/* primer77.c - poredjenje niski - KMP-algoritam */ #include #include #define EOS '\0' // simbol kraja niske #define MAXP 10 // max. duzxina obrasca #define MAXT 1000 // max. duzxina teksta void preprocpat( char *, int [] ); char *search( char *, char * ); int next[MAXP]; main(int argc, char *argv[]) { char pat[MAXP]; char text[MAXT]; char *mark; strcpy(pat, argv[1]); strcpy(text, argv[2]); preprocpat( pat, next ); mark = search( pat, text ); printf("%s\n", mark ); } void preprocpat( char *pat, int next[] ) { int i, j; i = 0; j = next[0] = -1; do { if( j==(-1) || pat[i]==pat[j] ) { i++; j++; next[i] = (pat[j]==pat[i]) ? next[j] : j; } else j = next[j]; } while( pat[i] != EOS ); } char *search( char *pat, char *text ) { int next[MAXP], j; if( *pat == EOS ) return( text ); preprocpat( pat, next ); for( j=0; *text != EOS; ) { if( j==(-1) || pat[j] == *text ) { text++; j++; if( pat[j] == EOS ) return( text-j ); } else j = next[j]; } return( NULL ); }