1. Си / Говнокод #1488

    +140

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    int  seek_substring_KMP  (char s[],   char q[])
	{ 
	int  i, j, N, M; 
	N = strlen(s); 
	M = strlen(q); 
	int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/ 
	/* Вычисление префикс-функции */ 
	i=0; 
	j=-1;
	d[0]=-1;
	while(i<M-1)
		{
		while((j>=0) && (q[j]!=q[i]))
			j = d[j];
		i++;
		j++;
		if(q[i]==q[j])
			d[i]=d[j];
		else
			d[i]= j;
		}
	/* поиск */
	for(i=0,j=0;(i<N)&&(j<M); i++,j++)
		while((j>=0)&&(q[j]!=s[i]))
			j=d[j];
	free (d);  /* освобождение памяти массива d */ 
	if (j==M)
		return i-j;
	else /* i==N */
		return -1;
	}

    Алгоритм Кнута — Морриса — Пратта. Жуже сложно реализвовать(

    Запостил: guest, 07 Августа 2009

    Комментарии (18) RSS

    • ava guest 07.08.2009 23:48 # 0

      daemon_master:
      почему? нормальный КМП, всего 31 строка:) на паскале он больше занимает
      Ответить

      • ava guest6 07.06.2024 07:52 # 0

        Почему больше? Эту программу можно перевести на Паскаль тупо заменой синтаксиса ( = на :=, а фигурных скобок — на begin и end).
        Ответить

    • ava guest 10.09.2009 00:33 # 0

      нужно ещё переменные осмысленней называть, и вы постигнете дзен
      Ответить

    • ava guest 24.11.2009 07:29 # +7

      Зип файль!
      Ответить

    • ava guest 03.04.2011 11:56 # +4

      14/88
      Ответить

    • ava guest6 07.06.2024 00:04 # 0

      Кнут, моррис и пратт охуели от такого си в духе 1991-го года
      Ответить

      • ava guest6 07.06.2024 00:24 # 0

        А что не так? Оыбчынй олимпиадный код.
        Ответить

        • ava guest6 07.06.2024 00:28 # 0

          в олимипиданом не было бы докстрок и free
          Ответить

          • ava guest6 07.06.2024 00:46 # 0

            Ну олимпиадник может в курсе, что в интырпрайзе нужно память чистить. Говорят, до такого могут на код-ревью доебаться.
            Ответить

            • ava guest6 07.06.2024 00:56 # 0

              Ну хорошо, а почему у него длинна строки это int?
              Это Борланд си под дос?

              Тогда нужно результат mallocа проверять: там куча мала совсем
              Ответить

    • ava guest6 07.06.2024 00:28 # 0

      - Милая, нам нужно серьезно поговорить.
      - Наконец-то ты повзрослел. Давай.
      - Как ты думаешь, кто сильнее: акула или медведь?
      Ответить

    • ava guest6 07.06.2024 01:08 # 0

      ..искать мы подстроку не бросим!
      Ответить

    • ava guest6 07.06.2024 15:49 # 0

      23-25 написаны некрасиво: счётчик j цикла for изменяется в теле. Лучше вынести j из преамбулы цикла for, раз уж мы её меняем в теле.
      Ответить

      • ava guest6 07.06.2024 16:13 # 0

        Спасибо огромное, обязательно переделаю!
        Ответить

        • ava guest6 08.06.2024 02:19 # 0

          Да не за что, пустяки.

          Ну как, переделал?
          Ответить

    Добавить комментарий