Алгоритмы поиска

int i, h, k, M, N, t_q, t_k;

N = strlen(s); М = strlen(q);

/* hisoblash h=(dM-l)mod p */

h=l; for(i=l; i

h=(h*d)%p;

/* Gorner sxemasi asosida tl va tq ni hisoblash */

t_q = 0; t_k = 0;

for(i=0; i

t_q = (d*t_q + q[i])% p;

t_k = (d*t_k + s[i])% p;

}

/* Formula asosida qator osti matnlarni taqqoslash(12)*/

for (k=0; k<=N-M; k++) {

if (t_q==t_k) {

for (i=0;(i

if (i==M) return k;

}

if (k

t_k = (d*(t_k-s[k]*h)+ s[k+M])% p;

if (t_k < 0) t_k + = p;

}

}

return -1;

}

7
mod 13
(а)

2

3

5

9

0

2

3

1

4 1

5

2

6

7

3

9

9

2

1

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
2	3	5	9	0	2	3	1	4	1	5	2	6	7	3	9	9	2	1

8

9

3

11

0

1

7

8

4

5

10

11

7

9

11

Namuna qidirish
Bo`sh qidiruv
…
…
…
(b)
mod 13

3

1

4

1

5

2

7

8

Yuqori razryad qiymati
Quyi razryad qiymati
(c)
(mod 13)
(mod 13)
(mod 13)
Yuqori razryad qiymati
Quyi razryad qiymati

Реализация алгоритма Бойера-Мура

int seek_substring_BM(unsigned char s[], unsigned char q[])

{ int d[256];

int i, j, k, N, M;

N = strlen(s);

M = strlen(q);

/* построение d */

for (i=0; i<256; i++)

d[i]=M; /* изначально М во всех позициях */

for (i=0; iM – i - 1 - расстояние до конца d */

d[(unsigned char)q[i]]= M-i-1;/* кроме последнего символа*/

/* поиск */

i= M-l;

do {

j = M-l; /* сравнение строки и образеца */

k = i; /* j – по образецу, k – по строке */

while ((j >= 0) && (q[j] == s[k])) {

k--; j--;

}

if (j < 0) return k+1; /* образец просмотрен полностью */

i+=d[(unsigned)s[i]];/*сдвиг на расстояние d[s[i]]вправо*/

} while (i < N);

return -1;

}