2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Поиск паттерна с помощью указателей
Сообщение22.11.2020, 23:44 
Прошу помочь разобраться.

Напишите функцию поиска первого вхождения шаблона в текст. В качестве первого параметра функция принимает текст (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;
}

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение22.11.2020, 23:59 
Аватара пользователя
Так просто идите по тексту, пока не найдёте его конец, и для каждой позиции в тексте проверяйте, не входит ли шаблон в текст начиная с данной позиции.
gogoshik в сообщении #1493797 писал(а):
Код:
if (count_p == l_p) {
  count = i;
  break;
}

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

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение23.11.2020, 00:32 
Спасибо. А думаете так красивее?

код: [ скачать ] [ спрятать ]
Используется синтаксис 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;
}

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение23.11.2020, 01:19 
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++);
 

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение23.11.2020, 03:04 
Все таки решил так.

код: [ скачать ] [ спрятать ]
Используется синтаксис 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;
}

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение23.11.2020, 03:28 
Аватара пользователя
Странное применение циклов 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; ...). Если этого не делать, тогда зачем он?

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение23.11.2020, 04:17 
StaticZero в сообщении #1493810 писал(а):
Если нет внутренних переменных, которые удобно писать в первом блоке, то while семантически точнее:
Есть правило "два из трёх": если у вас непусты хотя бы два из трёх элементов заголовка for, то надо использовать for, в противном случае надо использовать while. Конечно, это не абсолют, и, например, в данном случае while смотрится лучше, но вообще есть вот такое правило.

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение23.11.2020, 12:53 
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;
}

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение25.11.2020, 00:58 
Аватара пользователя
Меня немного смущает, что входные аргументы-указатели сдвигаются внутри функции. Если функция не предусматривает изменения входных данных, я бы делал char const* const

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение25.11.2020, 01:44 
Аватара пользователя
photon в сообщении #1494024 писал(а):
Меня немного смущает, что входные аргументы-указатели сдвигаются внутри функции
Так указатели же по значению передаются.

 
 
 
 Re: Поиск паттерна с помощью указателей
Сообщение25.11.2020, 02:01 
Аватара пользователя
Да, виноват

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group