Выпадение шаблона в массивах

Question

Мне поручено написать программу, которая подсчитывает количество раз, когда последовательность символов встречается в другой последовательности символов. Функции «pattern» должны возвращать количество повторений первой последовательности во второй последовательности без повторения. Поскольку это упражнение по программированию, я не могу использовать скобки для разыменования указателей и должен использовать только арифметику указателя.

Я решил использовать операторы if, чтобы увидеть, существует ли последовательность в массиве. Мне тяжело видеть, где мои проблемы. Я распечатываю pValue1, чтобы увидеть, где указатель находится в массиве. Любая помощь будет оценена по достоинству.

#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

Ваш сравнительный код довольно запутанный. Эта линия, вероятно, не делать то, что вы ожидаете, что делать:

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

Это разыменовывает каждый указатель, а затем добавляет 2 к результату. Я думаю, что вы предназначен этот:

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

Принимая это как намерение, код по-прежнему не так. Во-первых, вы сравните символы на [0]:

if (*pValue1 == *pValue2) 

Затем увеличиваем указатели, и сравнить символы в [1]:

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

Затем проверьте символы в [3] :

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

Итак, вы пропускаете [2], и вы проверяете только несколько символов. Вам нужен цикл, чтобы проверить все в первой строке с пятном , вы проверяете вторую строку.

Кроме того, вы, кажется, звоните pattern(), чтобы проверить всю строку ? Но тогда вы только проверяете его начало. Вам нужен внешний цикл для повторения каждой части второй строки.

Первые строки в main() обычно записывается следующим образом:

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

Я также рекомендую переименовать аргументы needle и haystack, чтобы сделать код более читаемым.

Answer 2

Использование арифметики указателя обычно является болью, поскольку использование указателей в целом опасно и требует особой осторожности, чтобы избежать проблем. Я предлагаю вам найти возможное решение, делающее более мелкие шаги и гарантируя, что вы поняли каждый из них.

Начнем со скелетом вашей программы:

#include <stdio.h> 

/* declaration of functions */ 

int main(void) { 

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

return 0; 
} 

Вы работаете с нулем массивов символов, и вы можете объявить и инициализировать их во многом (но не так, как вы это сделали ...):

/* declaration of global variables */ 

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

Чтобы решить задачу, я бы реализовать простой (но неэффективный) алгоритм, но, прежде чем прыгать на саму функцию, я постараюсь написать что-то легко проверить вашу (и мое тоже) понимание указатели. Например, напишите функцию, которая подсчитывает количество символов в этих массивах, кроме нулевого терминатора. Если вы не можете, посмотрите на это:

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

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

Обратите внимание, как он проверяет указатель, передаваемый в качестве параметра, прежде чем использовать его и как он вычисляет длину, используя некоторые арифметические операции над указателями. Это уродливо, но, похоже, это работает. Если все понятно (и проверено! Всегда убедитесь, что функция выполняет свое задание), давайте перейдем и напишем функцию, которая ищет символ внутри массива и возвращает позицию его первого вхождения в виде целого числа (или -1, если нет):

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

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

Снова проверьте его и попытайтесь понять, как это работает (или почему это не так). Теперь мы ближе. давайте превратить эту функцию так, чтобы она могла найти последовательность символов внутри массива и возвращает позицию его первого появления в виде целого числа (или -1, если нет):

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; 
} 

я добавил вложенный цикл, чтобы проверить corrispondence. Теперь у нас есть только выяснить все вхождения, и я буду использовать другую функцию, которая вызывает последний:

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; 
} 

Обратите внимание на ++ поз, чтобы начать поиск со следующей позиции. Вот так, просто переписать наши основные:

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

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

    getchar(); 

    return 0; 
}