Prefiks funksiya qurish algoritmlari. Kmp algoritmi

PREFIKS FUNKSIYA QURISH ALGORITMLARI.KMP ALGORITMI.

Prefiks funksiyasi (valiy funksiya) mavjud bo'lgan massiv berilgan. Ushbu funksiya, berilgan indeks orqali, ushbu indeksga qadar massivdagi barcha elementlarning yig'indisini topadi. Yuqoridagi tushunchaga asosan, quyidagi C++ kodi misol sifatida berilgan:

Bu kod asosan $n$` elementdan iborat bir massivni qabul qiladi va berilgan funksiya yordamida ularning prefiks summasini hisoblaydi. Prefiks summani hisoblash uchun bir valiy (prefix) massiviga loyiha maqsadli massivning birinchi elementini yozadi va kelayotgan har bir elementni - oldingi element va joriy element yig'indisini olib yozadi. Kodning chiquqicha qismida natijani konsolga chiqarish uchun yordamchi kod qo'llanilgan.

#include

using namespace std;

void prefix_sum(int arr[], int n, int prefix[]) {

prefix[0] = arr[0];

for (int i = 1; i < n; i++) {

prefix[i] = prefix[i - 1] + arr[i];

}

}

int main() {

int arr[] = {1, 2, 3, 4, 5};

int n = sizeof(arr) / sizeof(arr[0]);

int prefix[n];

prefix_sum(arr, n, prefix);

for (int i = 0; i < n; i++) {

cout << prefix[i] << " ";

}

return 0;

}

Prefiks funksiyasi, matematikada bir funksiya turi hisoblanadi. Bu funksiya, bir stringning har bir indexidan kirib chiqib, ularning har bir prefiksining ularning ularning ichidagi eng katta common elementlarining orta uzunligini hisoblaydi.

Bu koding string s ning har bir index uchun ushbu stingning prefiks funksiyasini topadi. Ushbu koding ishga tushirilgacha p[] arrayida tashrif buyurilishi kerak bolgan indexlar saqlaniladi.

#include

using namespace std;

void pref(string s, int p[]) {

p[0] = 0;

int n = s.size();

for(int i=1; i int j = p[i-1];

while(j>0 && s[i]!=s[j])

j = p[j-1];

if(s[i]==s[j])

j++;

p[i] = j;

}

}

int main() {

string s;

cin>>s;

int n = s.size(), p[n];

pref(s,p);

cout<<"Prefix function values for the given string are:\n";

for(int i=0; i cout< cout< return 0;

}

Perfiks funksiya, ​​berilgan raqam, agar uning barcha bo'luvchilari yig'indisi raqamning o'ziga teng bo'lsa, "mukammal raqam" deb ataladi. Masalan, 6 mukammal son, chunki uning bo'luvchilari yig'indisi (1, 2, 3) 6 ga teng.

#include using namespace std; bool isPerfect(int num) { // mukammallik soni nazorati int sum = 0; // bo'luvchilar yig'indisi for(int i = 1; i <= num/2; i++) { // takrorlashlar sonining yarmi if(num % i == 0) { // bo'luvchilarni qo'shing sum += i; } } if(sum == num) { // Jami songa tengmi? return true; } else { return false; } } int main() { int num; cout << " Raqam kiriting: "; cin >> num; if(isPerfect(num)) { cout << num << "mukammal raqam." << endl; } else { cout << num << "Bu mukammal raqam emas." << endl; } return 0; }

Bu kod foydalanuvchidan raqam oladi va isPerfect() funksiyasi yordamida bu raqam mukammal raqam ekanligini tekshiradi. isPerfect() funktsiyasi sonning bo'luvchilari yig'indisini qaytaradi va bu yig'indi raqamga teng yoki yo'qligini tekshiradi. Agar teng bo'lsa, funktsiya rostni qaytaradi va main() funksiyasi bu raqamni mukammal raqam sifatida chop etadi. Agar yo'q bo'lsa, u noto'g'ri va qaytaradi

//Berilgan satrda takrorlanuvchi pastki satrlar sonini topishga misol: #include using namespace std; void lpsArr(string& pat, vector& lps) { int len = 0; int i = 1; int n = pat.length(); lps.resize(n); lps[0] = 0; while (i < n) { if (pat[i] == pat[len]) lps[i++] = ++len; else { if (len != 0) len = lps[len - 1]; else lps

KMP (Knuth-Morris-Pratt) algoritmi berilgan matnda pastki matn mavjudligini topish uchun ishlatiladigan qatorli qidiruv algoritmidir. Bu algoritm O(n) vaqt murakkabligi va O(m) qoʻshimcha xotiradan foydalanishga ega, bu yerda n asosiy satr uzunligi va m pastki qator uzunligi. KMP algoritmi belgilarni solishtirishda ikkita indeksdan foydalanadi: i va j. Indeks i asosiy katalog indeksini, j indeksi esa pastki qator indeksini ifodalaydi. Agar pastki qatordagi belgi mos kelmasa, algoritm i indeksini oshiradi, lekin j indeksini o'zgartirmaydi. Bunday holda, agar pastki qator boshidan j indeksiga mos keladigan belgi mavjud bo'lsa, u i indeksini qaytaradi va pastki qatorning mos keladigan qismida boshqa moslikni qidiradi.

KMP algoritmining asosiy afzalligi shundaki, pastki satr uzunligi satrni qidirish uchun sarflangan vaqtga ta'sir qilmaydi. Buning sababi, KMP belgilarni taqqoslashda yaroqsiz indekslarni o'tkazib yuboradi. Bundan tashqari, xotiradan foydalanish juda past, chunki algoritm faqat asosiy satr uzunligi va pastki qator uzunligi uchun qo'shimcha xotiradan foydalanadi. Xulosa qilib aytadigan bo'lsak, KMP algoritmi matndagi pastki matnni topishning tez va samarali usulini ta'minlovchi qatorli qidiruv algoritmidir. Ushbu algoritmning afzalligi shundaki, pastki satr uzunligi belgilarni taqqoslashda noto'g'ri indekslarni o'tkazib yuborish orqali satrni qidirishga sarflangan vaqtga ta'sir qilmaydi.

Prefiks funktsiyasini hisoblash uchun quyidagi algoritmni yozish mumkin vector prefix_function (string s) { int n = (int) s.length(); vector pi (n); for (int i=0; i