|
Mustaqil ish mavzu: Marshurutlar va ularning vazifalari Qabullagan: Bajargan: nukus-2024
|
| bet | 5/5 | | Sana | 20.05.2024 | | Hajmi | 254,53 Kb. | | #244908 |
Bog'liq marshrutif(flag==0)
{
cout<<" Indeksda berilgan satr osti topildi:"<
}
}
/*oldingi ichki satrdan birinchi belgini olib tashlash orqali keyingi ichki satrning xesh qiymatini toping va keyingi satrni oldingi satr oxiriga qo'shing*/
/*xesh qiymatlarini topish uchun O (1) vaqt kerak bo'ladi*/ if(i
{
t=(d*(t-text[i]*h)+text[i+m])%q; if(t<0)
{
t=(t+q);
}
}
}
}
int main()
{
/*oʻzgaruvchilarni kiritish*/ string text;
cin>>text; string pattern;
cin>>pattern; rabin_karp(text,pattern,97); return 0;
}
Boyer-Mur algoritmi. 1977-yilda Robert Boyer va Jey Mur tomonidan ishlab chiqilgan, matnda oldindan ishlov berish imkoniyati bo'lmagan taqdirda, satrda qismiy satrni topish algoritmlari orasida eng tezkori hisoblanadi.
Algoritm gʻoyasi quyidagicha:
Chapdan o'ngga skanerlash, o'ngdan chapga taqqoslash.
To'xtash belgisini topish
agar taqqoslanadigan birinchi harf mos kelmasa, shablon eng yaqiniga o'tkaziladi
to'xtash belgisi bo'lmasa, shablon uning orqasiga siljiydi
Mos keladigan qo'shimchani topish
agar 1 yoki undan ortiq belgi mos kelsa, shablon bu qo'shimchaning birinchi mos kelishiga qadar o'ngga siljiydi
q w t e e q e w q r w q w r q r q w r q r
q w t e e q e r q r w q w r q r q w r q r
q w t e e q e w q r w q w r q r q w r q r
q w t e e q e w q r w q w r q r q w r q r
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
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)
{
}
else
}
cout << s << endl;
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
s += max(1, j - badchar[txt[s + j]]);
}
string txt= "ABAAABCD"; string pat = "ABC"; search(txt, pat);
return 0;
}
int main()
{
String txt= "ABAAABCD"; string pat = "ABC"; search(txt, pat);
return 0;
}
|
| |
