Претраживање и провера постојања садржаја стринга¶

Претраживање стрингова¶

У групу метода за претраживање стрингова могу да се уброје следећи методи:

• Contains: проверава да ли текућа инстанца стринга садржи наведени карактер или стринг

• IndexOf: враћа позицију првог појављивања датог карактера или стринга у текућој инстанци стринга

• IndexOfAny: враћа позицију првог појављивања било ког од наведених карактера у текућој инстанци стринга

• LastIndexOf: враћа позицију последњег појављивања датог карактера или стринга у текућој инстанци стринга

• LastIndexOfAny: враћа позицију последњег појављивања било ког од наведених карактера у текућој инстанци стринга

Подсећамо да је метод IndexOf коришћен у првом разреду, а методи IndexOfAny, LastIndexOf, LastIndexOfAny су му веома слични. Ови методи се разликују по томе да ли претражују од дате позиције налево или надесно, и да ли проналазе одређени карактер, подстринг, или било који од више наведених карактера.

На пример, метод LastIndexOfAny тражи од дате позиције налево (уназад) било који од датих карактера. Може се ограничити и број позиција које се претражују, а ако се то не учини, подразумева се тражење до почетка стринга. Ако тражена позиција не постоји, метод враћа -1. Ево како то изгледа на примеру:

Програм исписује

Tekst: Na 3 mesta u ovom tekstu se pojavljuju cifre: 2 ovde i 1 na pocetku.
Poslednja pojavljivanja neke cifre:
- Poslednje ukupno: na poziciji 55.
- Poslednje od poz. 15: na poziciji 3.
- Poslednje od poz. 15 u narednih 5 karaktera: na poziciji -1.
- Poslednje od poz. 1: na poziciji -1.

Прођите детаљно кроз дати пример и објасните резултат. То ће вам помоћи да употребите било који од поменутих метода за претраживање, када се за тиме укаже потреба.

Међу методе за претраживање стринга смо уврстили и метод Contains. Овај метод можемо да користимо када нас не интересује тачна позиција неког карактера или стринга у полазном стрингу, већ само да ли полазни стринг садржи тај карактер, односно стринг.

Мада методи IndexOf, LastIndexOf и Contains могу лако да се имплементирају помоћу двоструке петље, још једном вам скрећемо вам пажњу да су имплементације метода из библиотеке знатно ефикасније од тога, што је нарочито важно када су дужина \(N\) полазног и дужина \(M\) траженог стринга велике. Наиме, ови методи могу да се имплементирају (а у стандардној библиотеци су засигурно и имплементирани) тако да је број операција потребних за њихово извршавање сразмеран са \(M+N\), док би број операција у случају двоструке петље био сразмеран са \(M \cdot N\).

Два позната начина да се претрага стринга обави у линеарном времену су алгоритам KMP, скраћено од Кнут, Морис, Прат (Knuth, Morris, Pratt algorithm) и Бојер-Муров алгоритам (Boyer-Moore algorithm). О тим алгоритмима ће бити више речи у последњем поглављу овог курса.

Имајући у виду ефикасност метода за претрагу стринга, пожељно је да проблем који решавамо сведемо на примену неког од метода из библиотеке, када је то могуће.

Пример¶

Дата су два стринга, дужине до 50000 карактера. Проверити да ли први од њих може да се добије ротирањем другог за одређени број места улево. Ако може, одредити најмањи такав број места. На пример, ако су дати стрингови TRAVA и VATRA, ротирањем другог стринга за 2 места улево се добија први стринг, па је тражени број 2.

За једноставно и временски ефикасно решење кључно је да се примети следеће: ако дате стрингове означимо са s1 и s2, задатак се своди на проверу да ли су стрингови s1 и s2 исте дужине и затим на одређивање позиције првог појављивања стринга s1 у стрингу s2+s2, ако појављивање постоји.

Напишите програм који решава задатак по овој идеји.

Описано решење, истина, заузима непотребно много меморије за формирање стринга s2+s2, али зато са свега пар линија кода добијамо алгоритам линеарне сложености.

Провера постојања садржаја стринга¶

У ову групу смо уврстили методе IsNullOrEmpty и IsNullOrWhiteSpace.

• IsNullOrEmpty је статички метод класе String, који враћа вредност true ако је стринг прослеђен методу једнак null или једнак са "" (празним стрингом), а иначе враћа вредност false.

• IsNullOrWhiteSpace је метод сличан претходном, само што враћа true још и када стринг садржи само белине. Под белином се најчешће подразумева размак (space), али се назив белина односи и на друге карактере.

На пример, за следеће вредности стринга s функције дају ове резултате:

Једна типична употреба ових метода је на почетку нашег метода који је примио стринг s као параметар. На пример:

static void f(string s)
{
    if (string.IsNullOrEmpty(s))
        return;

    ...
}

На овај начин обезбеђујемо да у наставку (уместо три тачке), стринг можемо да користимо знајући да он постоји и није празан.