Algoritmul în sine este foarte simplu, în principiu. Există două linii. De exemplu, "Hello World" și "lo"
Vor lucra în două cicluri:
- Prima trecere se va efectua toate șir, și căutați locația dorită a primului șir de caractere ( „lo“).
- În al doilea rând, începând cu prima literă a găsit poziția - care a verifica scrisorile sunt după ea, și cât de multe dintre ele sunt la fel într-un rând.
Să ilustrăm căutarea subșir:
În primele două iterații ale ciclului de litere comparativ nu se potrivesc (roșu). In a treia repetare litera dorită (primul caracter al cuvântului dorit) a coincis cu caracter din șirul fiind completat. Atunci când o astfel coincidență este inclusă în a doua operație ciclu. Acesta este conceput pentru a contoriza numărul de caractere după primul din șirul de căutare, care se va potrivi cu caracterele din șirul original. Dacă unul dintre aceste personaje nu este același lucru - ieșirile buclă. Nu are nici un sens să conducă ciclul de deșeuri, după prima diferența, pentru că este clar că se dorește aici.
În a treia repetare potrivire doar primul caracter al șirului, dar al doilea nu este același lucru. Vom avea primul ciclu continua. A patra iterație dă rezultatele cerute - la fel ca toate caracterele din șirul de căutare cu o parte din șirul inițial. Și dacă toate caracterele din linie - subșir găsit. Algoritmul de operare poate fi completat.
Să vedem cum arată un cod de căutare subșir clasic într-un șir de caractere în C ++:
Căutare subșir
Două cicluri efectuate in fiecare sarcina lui. Un strivindu pe linie în speranța de a găsi „cap“ cuvânt de căutare (primul caracter). Al doilea întreabă dacă nu este găsit după „cap“, „corpul“, a titlului. Mai mult decât atât, se verifică dacă acesta este „corpul“ la capătul liniei. Ie nu este găsit în cazul în care lungimea cuvântul este unul mai mare decât lungimea necesară a unei linii, având în vedere că terminatorul Nul ( „\ 0“) se încadrează în această unitate.
Vedem că programul a găsit începutul pa subsirului în celulele șirului de caractere la indexul 0 și 4. De ce? La urma urmei, într-un cuvânt parapapa 3 din subșir. Toată problema este „\ 0“.
Mai multe detalii despre acest lucru
Faptul că caracterele C-siruri stocate în matrice de caractere. Fiecare linie este caracterizată prin așa-numita proprietate ASCIIZ. Această abreviere este literalmente tradus ca „șir de caractere care se termină caracterul cu codul zero“ - zero ASCI.
Captura este că, în cazul în care căutarea este în capătul liniei, este necesar să se ia în considerare este zero. Este, de asemenea, parte a liniei, iar acest algoritm, de asemenea, coincide cu sfârșitul șirului.
De exemplu, linia: „Amintiți-vă Harry camera numărul“ și „cameră“, de fapt, arata ca „Harry Amintiți-vă camera numărul \ 0“ și „cameră \ 0“. În cazul în care '\ 0'. caracter cu codul 0, care spune că șirul sa încheiat. Prin modul în care această abordare și vă permite să scrie astfel de cicluri ca:
Dacă dorim să găsim camera cuvânt. În picioare, în mijlocul unui cuvânt, avem nevoie doar de a compara 4 caractere, dar dacă dintr-o dată este necesar să se întâlnească doar la sfârșitul - nu ar trebui să compare 4 caractere, și ... 5. Sau, verificați pentru a vedea dacă după terminator nul. Aceasta nu este o afacere mare. Prin această linie trebuie doar să te obișnuiești.
În general, sensul algoritmului este de peste. Nu mai multe dificultăți decât zero la sfârșitul liniei de acolo. Cu toate acestea, ar trebui să acorde o atenție la multitudinea de căutare. Ce se întâmplă dacă avem nevoie pentru a găsi linia în poziții multiple? De câte ori apare termenul de căutare în linie și în ce locații? Aceasta este ceea ce este destinat să controleze al treilea parametru - int n - numărul de apariții ale unui șir de caractere. Dacă pui o acolo - el găsește prima apariție a titlului. În cazul în care cele două, se va face primul ciclu sari peste prima găsit, și să caute un al doilea. În cazul în care trei - pentru a căuta a treia și așa mai departe. Cu fiecare cuvânt de căutare a găsit, acest contor este decrementat evenimente. Acest lucru vă permite să descrie căutarea în ciclul: