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
|
q t e e q r w q w r e e
q w r q r
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
|
q t e e q r w q w r e e
q w r q r
q t e e q r w q w r e e
q w r q r
q t e e q r w q w r e e
q w r q r
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.
Do'stlaringiz bilan baham: |