-1

I had written a program of pattern matching in 'c' language. But it always show me the wrong output. Using the same to same logic I had written the code in 'c++' language & it works perfectly well there but not in 'c'.

According to my program, firstly I need to enter the size of the "text" & "pattern" that I want to enter. Then according to the size, the character array should store the corresponding number of characters in it using for loop. But for ex. if I enter the size of text to be 5, it stores only 2 characters & then displays a wrong answer further.

#include<stdio.h>
int p, t, c, LOC, i, j;

void main()

{

printf("Enter size of Text and Pattern\n");

scanf("%d %d",&t,&p);

char pat[p];

char txt[t];

    printf("Enter the Text\n");
    for(i=0;i<t;i++)
        {
            scanf("%c",&txt[i]);
        }
    printf("Enter the Pattern\n");
    for(i=0;i<p;i++)
        {
            scanf("%c",&pat[i]);
        }
    int MAX=t-p+1;


    for(i=0;i<MAX;i++)
    {
        int count=0;
        c=0;
           for(j=i;j<i+p;j++)
            {
                if(pat[count]==txt[j])
                {
                    count++;
                    c++;
                }
                else
                    break;
            }
           if(c==p)
            {

                LOC=i+1;
                break;
            }
    }
    if(LOC!=0)
        printf("Pattern found at location: %d",LOC);
    else
       printf("NOT FOUND\n");
}

Expected:

Enter size of Text and Pattern

5 2

Enter the Text

abbca

Enter the Pattern

bc

Pattern found at location: 3

Actual:

Enter size of Text and Pattern

5 2

Enter the Text

abb

Enter the Pattern

a

NOT FOUND
bruno
  • 32,421
  • 7
  • 25
  • 37
CodeBlood
  • 1
  • 1
    The first character read by `scanf("%c",&txt[i])` is the newline left over from the previous `%d` input. Please see [scanf() leaves the newline char in the buffer](https://stackoverflow.com/questions/5240789/scanf-leaves-the-new-line-char-in-the-buffer). – Weather Vane Feb 02 '19 at 10:08

2 Answers2

0
for(i=0;i<t;i++)
    {
        scanf("%c",&txt[i]);
    }

if you enter too much characters when Enter the text, I mean a string with more that t characters, the extra characters will be used for the pattern. Note also the \n will be read among them

to not have that problem when reading string(s)/characters(s) after other elements I encourage you to read a line each time.

Warning : the size of pat and txt must be one more to be able to memorize the terminating null char

You can do that :

int main()
{
  char  *line;
  size_t n;

  printf("Enter size of Text and Pattern\n");
  line = 0;
  n = 0;
  if (getline(&line, &n, stdin) == -1) {
    puts("abort");
    return -1;
  }
  if (sscanf(line, "%d %d",&t,&p) != 2) {
    puts("invalid size of Text and Pattern");
    return -1;
  }
  free(line);

  char pat[p+1]; /* warning +1 */
  char txt[t+1]; /* warning +1 */
  char fmt[16];

  printf("Enter the Text\n"); 
  line = 0;
  n = 0;
  if (getline(&line, &n, stdin) == -1) {
    puts("abort");
    return -1;
  }

  sprintf(fmt, "%%%ds", t); /* makes the right format */
  if ((sscanf(line, fmt, txt) != 1) || (strlen(txt) != t)) {
    puts("txt is too small");
    return -1;
  }
  free(line);

  printf("Enter the Pattern\n");
  line = 0;
  n = 0;
  if (getline(&line, &n, stdin) == -1) {
    puts("abort");
    return -1;
  }
  sprintf(fmt, "%%%ds", p); /* makes the right format */
  if ((sscanf(line, fmt, pat) != 1) || (strlen(pat) != p)) {
    puts("pat is too small");
    return -1;
  }
  free(line);

  int MAX=t-p+1;
  ...

Execution :

Enter size of Text and Pattern
5 2
Enter the Text
abbca
Enter the Pattern
bc
Pattern found at location: 3

Under valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out
==5185== Memcheck, a memory error detector
==5185== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5185== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5185== Command: ./a.out
==5185== 
Enter size of Text and Pattern
5 2
Enter the Text
abbca
Enter the Pattern
bc
Pattern found at location: 3==5185== 
==5185== HEAP SUMMARY:
==5185==     in use at exit: 0 bytes in 0 blocks
==5185==   total heap usage: 5 allocs, 5 frees, 2,408 bytes allocated
==5185== 
==5185== All heap blocks were freed -- no leaks are possible
==5185== 
==5185== For counts of detected and suppressed errors, rerun with: -v
==5185== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

Notes :

  • better to add a \n after you print the position
  • you complicate the program asking for the text and pattern sizes before to read them, you don't need to know their size before to read them, just use allocated memory in the heap like getline does rather than to put them in the stack using sizes unknown at compile time
bruno
  • 32,421
  • 7
  • 25
  • 37
-1

You use scanf(%c) to catch extra \n due to enter

#include<stdio.h>
int p, t, c, LOC, i, j;
char dummy;

void main()

{

printf("Enter size of Text and Pattern\n");

scanf("%d %d",&t,&p);
scanf("%c", &dummy);

char pat[p];

char txt[t];

printf("Enter the Text\n");
for(i=0;i<t;i++)
    {
        scanf("%c",&txt[i]);
    }

scanf("%c", &dummy);
printf("Enter the Pattern\n");
for(i=0;i<p;i++)
    {
        scanf("%c",&pat[i]);
    }
int MAX=t-p+1;


for(i=0;i<MAX;i++)
{
    int count=0;
    c=0;
    for(j=i;j<i+p;j++)
        {
            if(pat[count]==txt[j])
            {
                count++;
                c++;
            }
            else
                break;
        }
    if(c==p)
        {

            LOC=i+1;
            break;
        }
}
if(LOC!=0)
    printf("Pattern found at location: %d\n",LOC);
else
printf("NOT FOUND\n");
}

Check this it works

Himanshu Bhoyar
  • 16
  • 2