4

I wrote this code and it works in some cases. Sometimes, however, it fails, and I just can't see why. Can someone please help me spot the error?

It works for: String: ishanthakkar ishan patter: ishan

But it fails for:

String: cpr ograming patter: cpr

Source:

#include <stdio.h>    
#include <stdlib.h>    
#include <string.h>

int *compute_prefix_function(char *pattern, int psize)
{
    int k = -1;
    int i = 1;
    int *pi = malloc(sizeof(int)*psize);
    if (!pi)
        return NULL;

    pi[0] = k;
    for (i = 1; i < psize; i++) {
        while (k > -1 && pattern[k+1] != pattern[i])
            k = pi[k];
        if (pattern[i] == pattern[k+1])
            k++;
        pi[i] = k;
    }
    return pi;
}

// This function find matching string in O(n) time, so iterate through text string only once, when unmatching character found; it proceed with next character and start comparing with first character of string to be searched i.e pattern

int kmp(char *target, int tsize, char *pattern, int psize)
{
    int i;
    int *pi = compute_prefix_function(pattern, psize);
    int k = -1;
    if (!pi)
        return -1;

    for (i = 0; i < tsize; i++) {
        while (k > -1 && pattern[k+1] != target[i])
            k = pi[k];
        if (target[i] == pattern[k+1])
            k++;

        if (k == psize - 1) {
            free(pi);
            return i-k;
        }
    }

    free(pi);
    return -1;
}

int main(int argc, const char *argv[])
{
    char target[200];
    char *ch = target;
    char pattern[20];
    int i;

    printf("Enter the string: \n");
    fgets(target,100,stdin);

    printf("Enter the string to be matched: \n");
    fgets(pattern,20,stdin);

    i = kmp(target, strlen(target), pattern, strlen(pattern)); 
    if (i >= 0)
        printf("matched @: %s\n", ch + i);

    getch();
    return 0;
}
6
  • 1
    Try to indent code correctly - no need of extra spaces. Commented Jun 10, 2013 at 12:11
  • 4
    Can you comment your code so that the intent of the various pieces is clear? A function like kmp() is not part of the standard computing lexicon as far as I know, and you only state that the program does "pattern matching" without ever specifying what that means. For all we know, the code could be correct as posted. Commented Jun 10, 2013 at 12:22
  • @ John: Sorry for inconvenience, I have added little description to understand the program. Actually I have not coded entire program, so I also have some confusion! Commented Jun 10, 2013 at 13:10
  • 2
    @JohnZwinck: kmp is unambiguously Knuth-Morris-Pratt in string algorithms.
    – Fred Foo
    Commented Jun 10, 2013 at 13:12
  • I have made some mistake in kmp() function. Because it work well for text string & pattern like jiahkhan & jiah and return -1 for jiah & jiahkhan Commented Jun 10, 2013 at 13:16

2 Answers 2

2

The fgets function reads and includes the ending CR (or CRLF) in the string.

Add a chomp() function, like

void chomp(char *s) {
    int n = strlen(s);
    while (n && (s[n-1]==10 || s[n-1]==13)) s[--n] = 0;
}

that removes any CR or LF at the end of the string.
Then chomp() pattern and target before calling kmp() (and after the scanf())

chomp(target);
chomp(pattern);

i = kmp(target, strlen(target), pattern, strlen(pattern)); 

the program should behave better.


Note: 10 is '\n' (LF) and 13 is '\r' (CR)

5
  • I though this should work! I tried removing CR an LF but in this case it works for none of the case! Commented Jun 11, 2013 at 3:28
  • Did you add the chomp function? Call it twice, for each variable, before the call to kmp? It works here...
    – Déjà vu
    Commented Jun 11, 2013 at 4:46
  • Yes I did it in another way! Thanks buddy ring0, you was very near to my solution :) Commented Jun 11, 2013 at 5:44
  • 2
    @ring0 Those should be written as '\n' for LF and '\r' for CR, shouldn't they? Also the string terminator is more clearly written as '\0'.
    – unwind
    Commented Jun 11, 2013 at 5:46
  • 2
    @unwind Agreed for the CR/LF, 10 and 13 are not that famous. As for the 0 vs '\0', I like to use 0 as many beginners see '\0' as a special character, while, in C, this is only the 1-byte integer value of zero. This helps to consider C from its basic principles.
    – Déjà vu
    Commented Jun 11, 2013 at 5:53
1

Got clue:

i = kmp(target, strlen(target), pattern, strlen(pattern)); 

was passing string length+1(for null character) so it was giving false result for some text string

i = kmp(target, strlen(target)-1, pattern, strlen(pattern)-1); 

works for all cases!

Thanks to all of you for your time!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.