kz-maxx

RU KZ
← Басты бет

Бор

Trie: string сақтау, insert, search, prefix count және массив арқылы реализация

Бор деген не?

Бор, немесе trie, — string-терді сақтайтын ағаш. Онда әр вершина қандай да бір prefix-ке сәйкес келеді.

root — бос string
edge — бір символ
root-тан жол — string немесе string prefix-і

Бор мына жағдайларда ыңғайлы:

  • string қосу
  • string бар ма тексеру
  • prefix бар ма тексеру
  • берілген prefix-пен басталатын string санын табу
  • сөздікпен жұмыс істеу

Мысал

Борға мына string-тер қосылған болсын: 

ab
abc
ac

Онда ортақ prefix a бір рет қана сақталады.

root
└── a
    ├── b
    │   └── c
    └── c

ab string-і b вершинасында аяқталады, abc string-і c вершинасында аяқталады, ac string-і басқа c вершинасында аяқталады.

Негізгі идея

String қосқанда символдар бойынша солдан оңға жүреміз. Егер керек transition жоқ болса, жаңа вершина жасаймыз.

current vertex v
current symbol c
transition жоқ болса → жаңа vertex жасаймыз
келесі vertex-ке өтеміз
соңында word end белгілейміз

Массив арқылы реализация

Кіші ағылшын әріптері a...z үшін массив қолдану ыңғайлы: 

int tr[N][26];

Мұнда:

tr[v][c] — v вершинасынан c символы бойынша қайда барамыз
егер tr[v][c] = 0 болса, transition жоқ
cnt[v] — v вершинасында қанша word аяқталады
pass[v] — v арқылы қанша word өтеді
idx — жасалған vertex саны
Әдетте root номері 0 болады. Жаңа вершина номерлері 1, 2, 3 болып кете береді.

Базалық массивтер

const int N = 1000005;

int tr[N][26];
int cnt[N];
int pass[N];
int idx;

Егер барлық қосылатын string ұзындықтарының суммасы S болса, бордағы vertex саны ең көбі S + 1.

Сондықтан N шамамен барлық string ұзындықтарының суммасы + 5 болуы керек.

Символды санға қалай айналдырамыз?

Кіші ағылшын әріптері үшін: 

int c = s[i] - 'a';

Сонда:

'a' → 0
'b' → 1
'c' → 2
...
'z' → 25

String қосу

insert функциясы string-ті борға қосады. 

void insert(string s) {
    int v = 0;

    pass[v]++;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
        pass[v]++;
    }

    cnt[v]++;
}

Соңында:

cnt[v]++ → осы vertex ішінде word аяқталады
pass[v]++ → осы vertex арқылы word өтеді

Толық string іздеу

String бар ма тексеру үшін, оның символдары бойынша борда жүреміз.

Егер бір жерде transition жоқ болса, string жоқ. Егер соңына жетсек, cnt[v] тексереміз. 

bool search(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return false;
        }

        v = tr[v][c];
    }

    return cnt[v] > 0;
}

Prefix тексеру

Берілген prefix-пен басталатын кем дегенде бір word бар ма, соны тексеру үшін prefix символдары бойынша жүреміз. 

bool startsWith(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return false;
        }

        v = tr[v][c];
    }

    return true;
}

Мұнда cnt[v] тексерудің қажеті жоқ, себебі бізге word end емес, path бар ма сол маңызды.

Берілген prefix-пен қанша word басталады?

Бұл үшін pass массиві керек. Ол vertex арқылы қанша word өткенін көрсетеді. 

int countPrefix(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return pass[v];
}

Нақты word қанша рет қосылды?

Бұл үшін cnt[v] қолданамыз. Ол v вершинасында қанша word аяқталатынын сақтайды. 

int countWord(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return cnt[v];
}

Массив арқылы бордың толық коды

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

int tr[N][26];
int cnt[N];
int pass[N];
int idx;

void insert(string s) {
    int v = 0;

    pass[v]++;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
        pass[v]++;
    }

    cnt[v]++;
}

bool search(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return false;
        }

        v = tr[v][c];
    }

    return cnt[v] > 0;
}

bool startsWith(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return false;
        }

        v = tr[v][c];
    }

    return true;
}

int countWord(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return cnt[v];
}

int countPrefix(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return pass[v];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    insert("ab");
    insert("abc");
    insert("ac");
    insert("ab");

    cout << search("ab") << '\n';
    cout << search("a") << '\n';
    cout << startsWith("a") << '\n';
    cout << countWord("ab") << '\n';
    cout << countPrefix("a") << '\n';

    return 0;
}

Мысал output

1
0
1
2
4

Неге:

  • search("ab") = 1, себебі word бар
  • search("a") = 0, себебі prefix бар, бірақ a word ретінде жоқ
  • startsWith("a") = 1, себебі a-дан басталатын word бар
  • countWord("ab") = 2, себебі ab екі рет қосылды
  • countPrefix("a") = 4, себебі 4 word-тың бәрі a-дан басталады

Word өшіру

Егер word бұрын қосылған болса, оны өшіруге болады. Path бойынша жүріп pass азайтамыз, соңында cnt азайтамыз. 

bool eraseWord(string s) {
    if (countWord(s) == 0) {
        return false;
    }

    int v = 0;

    pass[v]--;

    for (char ch : s) {
        int c = ch - 'a';

        v = tr[v][c];
        pass[v]--;
    }

    cnt[v]--;

    return true;
}
Бұл қарапайым версияда vertex-тер физически өшірілмейді, тек counter-лер азаяды.

insert / find / prefix командалары

Көп задачада query түрлері былай беріледі:

add s — string қосу
find s — толық string бар ма тексеру
pref s — prefix s-пен қанша string басталады

Query-лермен толық программа

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

int tr[N][26];
int cnt[N];
int pass[N];
int idx;

void insert(string s) {
    int v = 0;

    pass[v]++;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
        pass[v]++;
    }

    cnt[v]++;
}

int countWord(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return cnt[v];
}

int countPrefix(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return pass[v];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    while (q--) {
        string type, s;
        cin >> type >> s;

        if (type == "add") {
            insert(s);
        } else if (type == "find") {
            if (countWord(s) > 0) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        } else if (type == "pref") {
            cout << countPrefix(s) << '\n';
        }
    }

    return 0;
}

Input / Output

Input

7
add ab
add abc
add ac
find ab
find a
pref a
pref ab

Output

YES
NO
3
2

Цифрлар үшін бор

Егер string тек 0...9 цифрларынан тұрса, alphabet size 10 болады. 

int tr[N][10];

int c = ch - '0';

Бұл телефон номерлері туралы задачаларда жиі кездеседі.

Үлкен әріптер үшін бор

Егер тек үлкен әріптер A...Z болса: 

int tr[N][26];

int c = ch - 'A';

Егер alphabet үлкен болса

Егер символ көп болса, tr[N][alphabet] өте көп memory алуы мүмкін. Онда map немесе unordered_map қолдануға болады. 

vector<unordered_map<char, int>> tr;
Бірақ кіші ағылшын әріптері үшін массив тезірек және қарапайым.

Телефон номерлері conflict тексеру

Типтік задача: телефон номерлерінің тізімі бар. Бір номер екінші номердің prefix-і болып тұр ма, соны тексеру керек.

Мысалы: 

911
9112

Мұнда 911 — 9112-нің prefix-і, демек conflict бар.

Conflict тексеру идеясы

String қосқанда:

  • жолда келе жатып word аяқталатын vertex кездессек, ескі word жаңа word-тың prefix-і
  • қосу біткеннен кейін current vertex-тің child-тары болса, жаңа word ескі word-тың prefix-і

Conflict тексеру коды

int tr[N][10];
int cnt[N];
int idx;

bool hasChild(int v) {
    for (int c = 0; c < 10; c++) {
        if (tr[v][c] != 0) {
            return true;
        }
    }

    return false;
}

bool insertPhone(string s) {
    int v = 0;

    for (char ch : s) {
        if (cnt[v] > 0) {
            return false;
        }

        int c = ch - '0';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
    }

    if (cnt[v] > 0) {
        return false;
    }

    if (hasChild(v)) {
        return false;
    }

    cnt[v]++;

    return true;
}
false — prefix conflict табылды деген сөз.

Асимптотика

Операция Уақыт
Ұзындығы L string қосу O(L)
Ұзындығы L string іздеу O(L)
Ұзындығы L prefix тексеру O(L)
Prefix-пен word санын табу O(L)

Memory:

O(vertex саны * alphabet size)

tr[N][26] үшін memory шамамен: 

N * 26 * sizeof(int)

Бор қашан қолданылады?

көп string сақтау керек
string тез іздеу керек
prefix тез іздеу керек
prefix-пен басталатын string санын табу керек
prefix conflict тексеру керек
string dictionary керек

Типтік қателер

  • root — 0 вершина екенін ұмыту
  • 0-ді жаңа vertex ретінде қолдану, бірақ 0 root болып тұр
  • Жаңа vertex жасағанда idx арттырмау
  • Word end белгілеу үшін cnt[v]++ ұмыту
  • cnt пен pass шатастыру
  • N массив size-ын тым кіші алу
  • Цифрлар үшін tr[N][26] және ch - 'a' қолдану
  • Бірнеше test арасында массивтерді тазаламау

Test арасында борды қалай тазалаймыз?

Егер test көп болса, тек қолданылған vertex-терді тазалауға болады. 

void clearTrie() {
    for (int i = 0; i <= idx; i++) {
        for (int c = 0; c < 26; c++) {
            tr[i][c] = 0;
        }

        cnt[i] = 0;
        pass[i] = 0;
    }

    idx = 0;
}
Бұл бүкіл үлкен N массивін тазалағаннан тезірек.

Қысқа шаблон

const int N = 1000005;

int tr[N][26];
int cnt[N];
int pass[N];
int idx;

void insert(string s) {
    int v = 0;

    pass[v]++;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
        pass[v]++;
    }

    cnt[v]++;
}

int countWord(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return cnt[v];
}

int countPrefix(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            return 0;
        }

        v = tr[v][c];
    }

    return pass[v];
}

Ең бастысы

бор = prefix ағашы
root = 0
tr[v][c] = v вершинасынан c символы бойынша transition
cnt[v] = v ішінде қанша word аяқталады
pass[v] = v арқылы қанша word өтеді
insert/search/prefix O(string length) жұмыс істейді