Pattern Occurrence in Arrays

Question

I am tasked to write a program that counts the number of times a character sequence occurs in another character sequence. The 'pattern' functions should return the the number of times the first sequence occurs in the second sequence without repeating. As this is a programming exercise, I'm not allowed to use brackets to dereference the pointers and must only use pointer arithmetic.

I decided to use if statements to see if a sequence occurs in the array. I'm having a difficult time seeing where my issues are. I print out pValue1 to see where the pointer is located in the array. Any help would be appreciated.

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

int pattern(char *ptr1, char *ptr2)
{
char *pValue1 = ptr1;
char *pValue2 = ptr2;
int count = 0;
int occurrence = 0;

while (*pValue1 != '\0')
{
    if (*pValue1 == *pValue2)
    {
        if (*pValue1++ == *pValue2++)
        {
            if (*pValue1 + 2 == *pValue2 + 2)
            {
                printf("Occurence happens at Location: %d", count);
                occurrence++;

            }
        }
    }
    count++;
    pValue1 = pValue1 + count;
    printf("%d", pValue1);
}
/* Print number of occurrences. */
printf("number of occurrences: %i \n", occurrence);


}


void main()
{
char array1[] = "1','1','0','1','0','0','1','1','1','0','1','1','\0'";
char array2[] = "'1','0', '1', '\0'";


pattern(array1, array2);
getchar();
getchar();
}

Answer 1

Using pointer arithmetic is usually a pain, as using pointers in general is dangerous and requires extra care to avoid problems. I suggest you to reach a possible solution making smaller steps and assuring you have understood each one.

Let's start with a skeleton of your program:

#include <stdio.h>

/* declaration of functions */

int main(void) {

/* declaration of global variables */
/* main stuff */

return 0;
}

You are working with null terminated character arrays and you can declare and initialize them in many ways (but not how you did it...):

/* declaration of global variables */

char source[] = "110100111011";             
char pattern[] = { '1', '0', '1', '\0' };

To solve your task I would implement a simple (but inefficient) algorithm, but before jumping to the actual function, I'll try to write something easy to test your (and mine too) understanding of pointers. For example, write a function which count how many characters are in those arrays exept for the null terminator. If you can't, take a look at this one:

int charArrayLength ( char * str ) {
    char * pch;

    if (str) {
        pch = str;
        while ( *pch ) pch++;
        return pch - str;
    }
    else return 0;
}

Note how it checks the pointer passed as a parameter before using it and how it calculates the length by using some pointer arithmetic. It's ugly, but it seems to work. If it's all clear (and tested! always make sure that a function does its job) let's move on and write a function that searches a character inside an array and return the position of its first occurrence as an integer (or -1 if not):

int posCharInString ( char * c, char * str) {
    char * p;

    if (str && c) {
        p = str;
        while ( *p ) {
            if ( *p == *c ) return p - str;
            p++;
        }
    }
    return -1;
}

Again, test it and try to understand how it works ( or why it doesn't...). Now we are closer. let's transform this function so that it can search for a sequence of characters inside an array and return the position of its first occurrence as an integer (or -1 if not):

int posStringInString ( char * pat, char * str) {
char * p;
char * s;
char * k;

if (str && pat) {
    p = str;
    while ( *p ) {
        s = pat;
        k = p;
        do {
            if ( *s == *k ) {
                s++;
                k++;
            } else break;
        } while ( *s && *k);
        if ( *s ) p++;
        else return p - str;
    }
}
return -1;
}

I added a nested loop to check corrispondence. Now we only have to find out all the occurrences, and I'll use another function which calls the last one:

int occurrenceOfStringInString ( char * pat, char * str) {
    int sum = 0;
    int pos = 0;
    int posrel = posStringInString(pat,str);

    while (posrel != -1 ) {
        pos += posrel;
        sum++;
        printf("Occurrence: %i, position: %i\n",sum,pos);
        ++pos;
        posrel = posStringInString(pat,str + pos);
   }
   return sum;  
}

Note the ++pos to start searching from the next position. That's it, just rewrite our main:

int main(void) {
    char sequence[] = "110100111011";
    char pattern[] = "101";

    printf("Total occurrences: %i\n",occurrenceOfStringInString(pattern,sequence));

    getchar();

    return 0;
}

Answer 2

Your comparison code is rather confusing. This line is probably not doing what you expect it to do:

if (*pValue1 + 2 == *pValue2 + 2)

It dereferences each pointer, then adds 2 to the result. I think you intended this:

if (*(pValue1 + 2) == *(pValue2 + 2))

Taking that as the intent, the code is still wrong. First, you compare the characters at [0]:

if (*pValue1 == *pValue2)

Then you increment the pointers, and compare the characters at [1]:

if (*pValue1++ == *pValue2++)

Then you check the characters at [3]:

if (*(pValue1 + 2) == *(pValue2 + 2))

So, you're skipping [2], and you're only checking a few characters. You need a loop to check everything in the first string against the spot you're checking in the second string.

Also, you seem to be calling pattern() to check the entire second string? But then you're only checking the beginning of it. You need an outer loop to iterate across each part of the second string.

The first lines in main() would normally be written this way:

char array1[] = "110100111011";
char array2[] = "101";

I also recommend renaming the arguments to needle and haystack, to make the code more readable.