<prompt> Unaweza kuniambia wazo nyuma ya kamba ya Knuth-Morris-Pratt inayolingana na algorithm?  <response>: Algoriti ya Knuth-Morris-Pratt KMP ni algoriti inayolingana na mfuatano ambayo hutafuta mchoro ndani ya mfuatano mkubwa wa maandishi. Inatumia dhana ya kitendakazi cha kushindwa ili kuruka kwa ufanisi sehemu za maandishi ambazo haziwezi kulingana na mchoro.Wazo la msingi la algoriti ya KMP ni kuchakata awali mchoro na kuunda jedwali la thamani linaloonyesha ni herufi ngapi za kuruka mchoro ikiwa kutolingana kutatokea katika nafasi fulani. Jedwali hili linaitwa kazi ya kushindwa au meza ya mechi ya sehemu. Chaguo za kukokotoa za kutofaulu huundwa kulingana na mchoro wenyewe, na unaweza kukokotwa kwa muda wa Om, ambapo m ni urefu wa muundo.Mara tu chaguo la kukokotoa la kutofaulu kukokotolewa, algoriti inaweza kuitumia kutafuta kwa ufaafu muundo katika maandishi. Algorithm huanza kwa kupanga mwanzo wa muundo na mwanzo wa maandishi, na kisha inalinganisha wahusika kutoka kushoto kwenda kulia. Ikiwa ulinganifu utapatikana, kanuni husogea hadi kwa herufi inayofuata katika muundo na maandishi. Hata hivyo, ikipatikana kutolingana, kanuni hutumia chaguo la kukokotoa la kutofaulu ili kubainisha umbali wa kubadilisha mchoro kabla ya kurejesha ulinganisho.Algorithm ya KMP ina uchangamano wa wakati wa hali mbaya zaidi wa On m, ambapo n ni urefu wa maandishi. Hii ni haraka kuliko mbinu ya kutojua ya kulinganisha mifuatano yote inayowezekana, ambayo ina ugumu wa wakati wa hali mbaya zaidi wa Onm.Kwa ujumla, algoriti ya KMP ni algoriti yenye nguvu na bora ya kulinganisha kamba, na inatumika sana katika programu nyingi, kama vile vihariri vya maandishi na injini za utafutaji. Maelekezo: Ninawezaje kutekeleza algorithm hii katika nambari ya python? Jibu: Ili kutekeleza algorithm ya Knuth-Morris-Pratt huko Python, unaweza kufuata hatua hizi:Unda kipengele cha kushindwa:1. Anzisha safu ya ukubwa wa m urefu wa muundo ili kuhifadhi thamani za chaguo za kukokotoa za kushindwa.- Weka kipengele cha kwanza cha safu kuwa -1 na kipengele cha pili hadi 0.- Tumia viashiria viwili, i na j, ili kusisitiza juu ya muundo na kukokotoa maadili ya utendaji ya kushindwa.- Ikiwa herufi katika i na j zinalingana, weka kipengele kinachofuata cha chaguo la kukokotoa kuwa j1 na uongeze i na j.- Ikiwa herufi hazilingani na j 0, weka j kwa thamani ya utendaji kazi wa kutofaulu katika j-1 na ujaribu tena.- Ikiwa wahusika hawafanani na j 0, weka kipengele kinachofuata cha kazi ya kushindwa kwa 0 na kuongeza i.2. Tumia kitendakazi cha kutofaulu kutafuta mchoro katika maandishi:- Anzisha viashiria viwili, i na j, ili kusisitiza juu ya maandishi na muundo.- Wakati i 0, weka j kwa thamani ya utendaji kazi wa kushindwa katika j-1 na ujaribu tena.- Ikiwa herufi hazilingani na j 0, nyongeza i.Hapa kuna mfano wa kazi ya Python inayotekelezea algorithm ya KMP: chatudef kmpmaandishi, muundo: n lenzi maandishi m leni muundo kushindwa -1 m hesabu kitendakazi cha kutofaulu mimi 0 j 1 wakati j 0: i kutofaului-1 1 kwingine: j 1 tumia kitendakazi cha kutofaulu kutafuta mchoro katika maandishi mimi 0 j 0 mechi wakati mimi 0: j kutofauluj-1 1 kwingine: mimi 1 mechi za kurudiChaguo hili la kukokotoa huchukua mfuatano wa maandishi na mfuatano kama ingizo, na kurejesha orodha ya fahirisi ambapo mchoro unaonekana katika maandishi. 