Примитивный алгоритм поиска подстроки в строке

Как реализовать сабж на СИ? У меня без GOTO не выходит, туплю однако

 

http://ru.wikipedia.org/wiki/Алгоритм_Бойера_—_Мура

 

Не-не, мне нужен вот этот
http://ru.wikipedia.org/wiki/Поиск_подстроки
Принцип мне понятен, путаюсь в брейках и континью.

 

Код (Text):

1. #include <string.h>
2.  
3. int substr(char* haystack, char* needle)
4. {
5.     int i,j;
6.     int Lh = strlen(haystack);
7.     int Ln = strlen(needle);
8.     int L = Lh-Ln+1;
9.     for(i=0; i<L; ++i)
10.     {
11.         for(j=0; j<Ln; ++j)
12.             if(haystack[i+j] != needle[j])
13.                 break;
14.         if(j==Ln) break;
15.     }
16.     return (i==L) ? -1 : i;
17. }

 

luckysundog
конец строки можно определить и без подсчета ее длины

Код (Text):

1. int substr(char* str, char* sub)
2. {
3.   for (int i=0, j=0; str[i+j]&&sub[j]; (str[i+j]==sub[j])?j++:j=++i-i);
4. }

если ничего не путаю, то вот так

 

простите. для выяснения нашел или нет надо чуть изменить

Код (Text):

1. int substr(char* str, char* sub)
2. {
3.   int i,j;
4.   for (i=0, j=0; str[i+j]&&sub[j]; (str[i+j]==sub[j])?j++:j=++i-i);
5.   return sub[j]?i:-1;
6. }

 

имхо не стоит писать в таком стиле, где с первого взгляда непонятно что происходит

 

n0name
для меня вполне хватает названия функции чтобы понять что происходит в коде в две строчки и объявления 2-х переменных. к тому же в этом варианте отсутствуют лишние проходы на выяснение длин строк.

 

хотя то что генерит си все равно далеко от совершенства. тоже на асме у меня выходит куда короче

 

Спасибо! Есть даже из чего выбрать

 

Код (Text):

1. int SubStr(char* lpszSource, char* lpszSubStr)
2. {
3.     int i;
4.     int LenSource = lstrlenA(lpszSource);
5.     int LenSubStr = lstrlenA(lpszSubStr);
6.     if (LenSubStr > LenSource)
7.         return -1;
8.  
9.     for (i = 0; i < LenSource - LenSubStr + 1; i++)
10.     {
11.         if (RtlCompareMemory(lpszSource + i, lpszSubStr, LenSubStr) == LenSubStr)
12.             return i;
13.     }
14.  
15.     return -1;
16. }

Ну как вариант в догонку...

 

наоборот надо

 

x0man
те же овощи только в профиль

 

max7C4

ну а можно пойти дальше и вообще отказаться от счетчиков, используя только указатели это все прикольно конечно, но на сложность алгоритма к сожалению не влияет.

такие приколы красиво смотрятся, но по-моему легче перенести это ветвление в тело цикла и там просто присвоить j=0, чем делать такие выкрутасы. и если угодно, это тоже можно написать в две строчки, а то и в одну

тут же вспомнился XCHG через ксоры или через сложение. красиво, но вот нафига?

x0man

то же самое, только виндозависимое

 

насчет ++i - i интересно... будет ли компилятор на самом деле генерировать это вычитание или нет?

 

luckysundog
зависит от компиля. КЭП

 

luckysundog
проверил. WATCOM, Builder, VC, MinGW ни кто даже усом не повел и код везде одинаковый (на удивление)

Код (Text):

1. inc edx
2. mov eax, edx
3. sub eax, edx

хоть бы регистры порядком поменяли что ли

 

max7C4
оптимизацию то включил? или в дебаге собирали?

 

; 9 : int t;
; 10 : t=++argc-argc;
; 11 : return t;
xor eax, eax

VC 2008 ну короче все с товарищем max7C4 ясно

 

Код (Text):

1. ; 16   :    t=++i-i;
2.  
3.     inc DWORD PTR _i$[esp+4]
4.  
5. ; 17   :    printf("%d",t);
6.  
7.     push    0
8.     push    OFFSET $SG-79
9.     call    DWORD PTR __imp__printf

те так, а то первый раз я не обманул компиль