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

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

    • ava guest 07.08.2009 23:48 # 0

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

    • 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
      Ответить

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