18-mavzu. Chekli avtomat yordamida qismiy satrlarni qidirish To'xtatish belgisi jadvali

18-mavzu. Chekli avtomat yordamida qismiy satrlarni qidirish
To'xtatish belgisi jadvali. Qismiy satrdagi elementning oxirgi o'rnini belgilaydi (oxirgi harfdan tashqari). Agar qismiy satrda element bo'lmasa, jadvalga 0 kiritiladi (bittadan raqamlash uchun)
Misol. Qismiy satr: qwrqr

Simvol	q	w	r	e	t
Oxirgi pozitsiya	4	2	3	0	0

1. 
   q t e e q r w q w r e e
   q w r q r
   
2. 
   q t e e q r w q w r e e
   q w r q r
   

Suffiks jadvali. Mumkin bo'lgan barcha qo'shimchalar uchun jadvalda qismiy satrni o'zgartirish kerak bo'lgan eng kichik miqdor ko'rsatilgan, u yana qo'shimchaga mos keladi. Agar bunday siljishning iloji bo'lmasa, satrning uzunligi ko'rsatilgan.
Misol. Qismiy satr: qwrqr

Suffiks	Boʻsh	r	qr	rqr	wrqr	qwrqr
qadam	1	2	5	5	5	5

1. 
   q t e e q r w q w r e e
   q w r q r
   
2. 
   q t e e q r w q w r e e
   q w r q r
   
3. 
   q t e e q r w q w r e e
   q w r q r
   
4. 
   q t e e q r w q w r e e
   q w r q r
   

Algoritmning murakkabligi. O (| haystack | + | needle | + | Σ |) davriy bo'lmagan qismiy satrlar bo'yicha
O (| haystack | · | needle | + | Σ |) davriy
haystack - berilgan satr, needle – qismiy satr, Σ - solishtirish uchun alifbo
1991-yilda Koul shuni ko'rsatdiki, davriy bo'lmagan sxemalar bo'yicha, algoritm satr bo'ylab to'liq o'tishda 3·|haystack| tadan ko'p bo'lmagan taqqoslashni amalga oshiradi.
Boyer-Mura algoritmi (C++)
#include
using namespace std;
# define NO_OF_CHARS 256
void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS])
{
int i;
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0;
while(s <= (n - m))
{
int j = m - 1;
while(j >= 0 && pat[j] == txt[s + j])
j--;
if (j < 0)
{
cout << s << endl;
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
s += max(1, j - badchar[txt[s + j]]);
}
}
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
Mavzu yuzasidan savollar:
1. Qismiy satrlarni izlash algoritmi nima?
2. Qismiy satrlarni izlash algoritmlarini foydalanish samaradorligini taqqoslang
3. Suffiks jadvali nima?
4. Satrlar uchun xesh funksiyasini qoʻllang
5. Robin-Karp va Boyer-Mur algoritmlarini taqqoslang?
Mustaqil ishlash uchun masalalar:
1. C++ tilida xesh jadvallarni hosil qiling.
2. C++da xesh jadvallarning metodlarini qoʻllang.