Алгоритм Рабина-Карпа поиск строки в подстроке на Си - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Помогите пожалуйста нужно сделать поиск подстроки в строке из файла с помощью алгоритма Рабина-Карпа: Вот чтение из файла:
#include "header.h" //тут все библиотеки
#define In1NAME "text.txt"
int main ()
{
char *temp, 
      buf[256];
FILE *f1;
f1=fopen(In1NAME,"r");
 
//Открыли f1
    if (f1 == NULL)
        printf ("-> Ошибка чтения из файлов %s!\n",In1NAME);
    else printf ("\n-> Файл %s открыт: \n",In1NAME);

//Поместили в buf и разбили на слова f1
while(fgets(buf, sizeof(buf), f1)!=NULL);
//temp = strtok (buf, " \n");
printf ("%s\n",buf);
 
fclose(f1);
return 0;
}
Нашел несколько алгоритмов вот ссылки: http://e-maxx.ru/algo/rabin_karp http://algolist.ru/search/esearch/karp_rab.php может быть это не совсем то что нужно, я плохо разбираюсь в си и не могу понять как это вообще сделать если даже эти алгоритмы подходят. плиз помогите сделать лабу, очень прошу
плизз помогите

Решение задачи: «Алгоритм Рабина-Карпа поиск строки в подстроке на Си»

textual
Листинг программы
/* Return the offset of one string within another.
   Copyright (C) 1994,1996,1997,2000,2001,2003,2008 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
 
   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.
 
   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.
 
   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */
 
/* This particular implementation was written by Eric Blake, 2008.  */
 
#ifndef _LIBC
# include <config.h>
#endif
 
/* Specification of strstr.  */
#include <string.h>
 
#include <stdbool.h>
 
#ifndef _LIBC
# define __builtin_expect(expr, val)   (expr)
#endif
 
#define RETURN_TYPE char *
#define AVAILABLE(h, h_l, j, n_l)           \
  (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
   && ((h_l) = (j) + (n_l)))
#include "str-two-way.h"
 
#undef strstr
 
/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
   if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
   HAYSTACK.  */
char *
strstr (const char *haystack_start, const char *needle_start)
{
  const char *haystack = haystack_start;
  const char *needle = needle_start;
  size_t needle_len; /* Length of NEEDLE.  */
  size_t haystack_len; /* Known minimum length of HAYSTACK.  */
  bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
 
  /* Determine length of NEEDLE, and in the process, make sure
     HAYSTACK is at least as long (no point processing all of a long
     NEEDLE if HAYSTACK is too short).  */
  while (*haystack && *needle)
    ok &= *haystack++ == *needle++;
  if (*needle)
    return NULL;
  if (ok)
    return (char *) haystack_start;
 
  /* Reduce the size of haystack using strchr, since it has a smaller
     linear coefficient than the Two-Way algorithm.  */
  needle_len = needle - needle_start;
  haystack = strchr (haystack_start + 1, *needle_start);
  if (!haystack || __builtin_expect (needle_len == 1, 0))
    return (char *) haystack;
  needle -= needle_len;
  haystack_len = (haystack > haystack_start + needle_len ? 1
          : needle_len + haystack_start - haystack);
 
  /* Perform the search.  Abstract memory is considered to be an array
     of 'unsigned char' values, not an array of 'char' values.  See
     ISO C 99 section 6.2.6.1.  */
  if (needle_len < LONG_NEEDLE_THRESHOLD)
    return two_way_short_needle ((const unsigned char *) haystack,
                 haystack_len,
                 (const unsigned char *) needle, needle_len);
  return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
                  (const unsigned char *) needle, needle_len);
}
libc_hidden_builtin_def (strstr)
 
#undef LONG_NEEDLE_THRESHOLD

Объяснение кода листинга программы

Код представлен в виде функции поиска подстроки в строке, реализованной на языке C. Ниже приведён список описывающих его элементов:

  1. Return the first occurrence of NEEDLE in HAYSTACK.
  2. Return HAYSTACK if NEEDLE is empty, otherwise NULL if NEEDLE is not found in HAYSTACK.
  3. Подстрока, которую необходимо найти (NEEDLE).
  4. Строка, в которой осуществляется поиск (HAYSTACK).
  5. Длина подстроки (needle_len).
  6. Длина строки (haystack_len).
  7. Флаг, показывающий, что подстрока является префиксом строки.
  8. Определение длины подстроки с использованием strchr.
  9. Если подстрока пустая или её длина больше порогового значения, то происходит переход к алгоритму двухстороннего поиска.
  10. Если подстрока не пустая и её длина меньше порогового значения, то происходит возврат начальной позиции подстроки в строке.
  11. Если подстрока пустая, то происходит возврат начальной позиции строки.
  12. Если подстрока не пустая и её длина больше порогового значения, то происходит переход к алгоритму двухстороннего поиска.
  13. Алгоритм двухстороннего поиска для подстрок длиннее порогового значения.
  14. Алгоритм двухстороннего поиска для подстрок короче порогового значения.
  15. Алгоритм двухстороннего поиска для подстрок, являющихся префиксом строки.
  16. Алгоритм двухстороннего поиска для подстрок, не являющихся префиксом строки.
  17. Алгоритм двухстороннего поиска для подстрок, являющихся префиксом строки.
  18. Алгоритм двухстороннего поиска для подстрок, не являющихся префиксом строки.
  19. Алгоритм двухстороннего поиска для подстрок длиннее порогового значения.
  20. Алгоритм двухстороннего поиска для подстрок короче порогового значения. Элементы, которые могут быть непонятны из описания:
    • AVAILABLE - это функция-макрос, которая проверяет, есть ли ещё символы в строке после текущей позиции.
    • LONG_NEEDLE_THRESHOLD - это константа, которая определяет пороговое значение длины подстроки, при котором происходит переход к алгоритму двухстороннего поиска.
    • strchr - это функция, которая ищет первое вхождение символа в строке.
    • two_way_short_needle и two_way_long_needle - это функции, которые реализуют алгоритм двухстороннего поиска для подстрок короче и длиннее порогового значения соответственно.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.833 из 5
Похожие ответы