Поиск паттерна с помощью указателей

[gogoshik]

Прошу помочь разобраться.

Напишите функцию поиска первого вхождения шаблона в текст. В качестве первого параметра функция принимает текст (C-style строка), в которой нужно искать шаблон. В качестве второго параметра строку-шаблон (C-style строка), которую нужно найти. Функция возвращает позицию первого вхождения строки-шаблона, если он присутствует в строке, и -1, если шаблона в тексте нет. При выполнении данного задания вы можете определять любые вспомогательные функции, если они вам нужны. Вводить или выводить что-либо не нужно. Реализовывать функцию main не нужно.

Я решил эту задачу следующим образом. Но хотелось бы решить её полностью через указатели. Тогда точно не понадобилась бы функция strlen(). Плохо понимаю, как это сделать.

Используется синтаксис C++

int strlen(const char* s)
{
        int count = 0;
        while (*s) {
                ++count;
                ++s;
        }
        return count;
}

int strstr(const char* text, const char* pattern)
{
        if (*pattern == '\0') return 0;
        int l_t = strlen(text);
        int l_p = strlen(pattern);
        int count = -1;
        for (int i = 0; i < l_t; i++) {
                int count_p = 0;
                for (int j = 0; j < l_p; j++) {
                        if (text[i + j] == pattern[j]) {
                                ++count_p;
                        } else break;
                }
                if (count_p == l_p) {
                        count = i;
                        break;
                }
        }
        return count;
}

[mihaild]

Так просто идите по тексту, пока не найдёте его конец, и для каждой позиции в тексте проверяйте, не входит ли шаблон в текст начиная с данной позиции.

gogoshik в сообщении #1493797 писал(а):

if (count_p == l_p) {
  count = i;
  break;
}

Лучше сразу здесь и return написать.

[gogoshik]

Спасибо. А думаете так красивее?

Используется синтаксис C++

int strstr(const char* text, const char* pattern)
{
        if (*pattern == '\0') return 0;
        int l_t = strlen(text);
        int l_p = strlen(pattern);
        int count = -1;
        for (int i = 0; i < l_t; i++) {
                int count_p = 0;
                for (int j = 0; j < l_p; j++) {
                        if (text[i + j] == pattern[j]) {
                                ++count_p;
                        } else break;
                }
                if (count_p == l_p) return i;  
        }
        return count;
}

[oleg_2]

gogoshik
У Вас С++, но как-то всё по СИ-шному сделано. На СИ можно написать через указатели:

Используется синтаксис C

//   gcc tmp.c -o tmp.cgi -Wall -Werror -O3
//   ./tmp.cgi
//   ./tmp.cgi  "r* p"


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


//------------ poisk1 --------------
// obr -"образец", паттерн по-Вашему
int poisk1(const char *b, const char *obr)
{
    const char *p, *p1, *v;

    for(p1=b; *p1!=0; p1++){
        if(*p1 != *obr) continue;
        for(p=p1, v=obr; p!=0 && *p==*v; p++, v++);
        if(*v==0) return(p1-b);
    }
    return(-1);
}

//--------------- main ----------

int main(int argc, char const **argv)
{
    const char *p, *t="int strstr(const char* text, const char* pattern)";
    int i, d;

    if(argc<2){ printf("Err-arg\n"); exit(0);}
    p=argv[1];

    d=poisk1(t, p);

    printf("t=\"%s\"\n", t);
    for(i=0; i<(d+3); i++){ printf(" ");}
    printf("^\n");
    printf("p=\"%s\"\n", p);
    printf("d=\"%d\"\n", d);
    exit(0);
}

 

-- 23.11.2020, 03:01 --

Извините, допустил ошибку, нашёл её визуально, как-то работало и с ошибкой:

Используется синтаксис C

   -for(p=p1, v=obr; p!=0 && *p==*v; p++, v++);
   +for(p=p1, v=obr; *p!=0 && *p==*v; p++, v++);
 

[gogoshik]

Все таки решил так.

Используется синтаксис C++

int strstr(const char *text, const char *pattern)
{
  if (*pattern == '\0') return 0;
  int count = 0;
  for (; *text != '\0'; text++) {
    auto t = text;
    auto p = pattern;
    for (; *p != '\0'; p++) {
      if (*t == *p) ++t;
      else break;
    }
    if (*p == '\0') return count;
    ++count;
  }
  return -1;
}

[StaticZero]

Странное применение циклов for, имхо.

Используется синтаксис C

for (; *p != '\0'; p++) {
  if (*t == *p) ++t;
  else break;
}
 

Если нет внутренних переменных, которые удобно писать в первом блоке, то while семантически точнее:

Используется синтаксис C

while(*p != '\0' && *t == *p) {
  p++; t++;
}
 

или ещё более идиоматично, используя short-circuiting,

Используется синтаксис C

while(*p != '\0' && *t++ == *p++) {}
 

правда тут уже может пострадать читаемость, но это кому как.

Мне всегда казалось, что for удобен именно тем, что можно эффективно scope-ить переменные счётчиков: for(int i = 0; ...). Если этого не делать, тогда зачем он?

[warlock66613]

StaticZero в сообщении #1493810 писал(а):

Если нет внутренних переменных, которые удобно писать в первом блоке, то while семантически точнее:

Есть правило "два из трёх": если у вас непусты хотя бы два из трёх элементов заголовка for, то надо использовать for, в противном случае надо использовать while. Конечно, это не абсолют, и, например, в данном случае while смотрится лучше, но вообще есть вот такое правило.

[gogoshik]

StaticZero в сообщении #1493810 писал(а):

Если нет внутренних переменных, которые удобно писать в первом блоке, то while семантически точнее

С while можно сделать и так:

Используется синтаксис C++

while (*p && *t == *p) { ++p; ++t; }

Но думаю, что тут использование for или while семантически равнозначно. Я где-то читал, что если стоит вопрос, что выбрать, то хороший стиль -- это все таки for.

-- 23.11.2020, 13:14 --

Тоже будет работать.

Используется синтаксис C++

int strstr(const char *text, const char *pattern)
{
  if (!*pattern) return 0;
  int pos = 0;
  while (*text) {
    auto t = text;
    auto p = pattern;
    while (*p && *t == *p) { ++p; ++t; }
    if (!*p) return pos;
    ++pos;
    ++text;   
  }
  return -1;
}

[photon]

Меня немного смущает, что входные аргументы-указатели сдвигаются внутри функции. Если функция не предусматривает изменения входных данных, я бы делал char const* const

[mihaild]

photon в сообщении #1494024 писал(а):

Меня немного смущает, что входные аргументы-указатели сдвигаются внутри функции

Так указатели же по значению передаются.

[photon]

Да, виноват