📝 Низове и Търсене: Основи

Работата с текст е неизменна част от програмирането. В C++ основният инструмент за това е класът std::string.

1. Символи и ASCII

Компютрите работят с числа. Символите (char) се съхраняват като кодове (обикновено ASCII). * 'A' е 65, 'a' е 97, '0' е 48. * Разликата между малка и главна буква е 32 ('a' - 'A' == 32). * Цифра към число: int digit = c - '0';.

2. Класът std::string

За разлика от C-style низовете (char[]), std::string е динамичен, безопасен и лесен за употреба.

2.1. Вход и Изход

string s;
cin >> s; // Чете до първия интервал/нов ред!

Ако искате да прочетете цял ред (с интервалите):

string line;
getline(cin, line);

Важно: Ако преди getline сте ползвали cin >> x, в буфера е останал символ за нов ред, който getline ще "изяде" веднага (празен низ). Използвайте cin.ignore() преди getline.

2.2. Основни операции

string s = "Hello";

// 1. Дължина
int len = s.length(); // или s.size()

// 2. Достъп до символ (0-индексиран)
char c = s[0]; // 'H'
s[0] = 'h'; // "hello"

// 3. Добавяне
s += " World"; // "hello World"
s.push_back('!'); // "hello World!"

// 4. Подниз (начало, дължина)
string sub = s.substr(0, 5); // "hello"
string tail = s.substr(6);   // "World!" (до края)

// 5. Изтриване (начало, брой)
s.erase(5, 1); // Изтрива интервала на позиция 5

3. Търсене в низ

3.1. Вграденият метод find

Връща индекса на първото срещане или специалната константа string::npos, ако не е намерено.

string text = "banana";
size_t pos = text.find("ana");

if (pos != string::npos) {
    cout << "Found at index: " << pos << endl; // 1
} else {
    cout << "Not found" << endl;
}

// Търсене на следващо срещане
pos = text.find("ana", pos + 1); // Търси от индекс 2 -> намира на 3

Сложността на find в най-лошия случай е \(O(N \cdot M)\), но обикновено работи бързо.

3.2. Други методи за търсене

• rfind(str): Търси отзад напред (последно срещане).
• find_first_of("aeiou"): Намира първия символ, който е гласна.
• find_first_not_of(" "): Намира първия символ, който НЕ е интервал (за trim).

4. Конвертиране (Числа <-> Низове)

От Число към Низ

int x = 123;
string s = to_string(x);

От Низ към Число

string s = "456";
int x = stoi(s);       // String to Int
long long y = stoll(s); // String to Long Long
double z = stod(s);    // String to Double

5. Класически задачи

5.1. Палиндром

Проверка дали низ се чете еднакво отпред и отзад.

bool isPalindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) return false;
    }
    return true;
}

5.2. Анаграми

Два низа са анаграми, ако съдържат едни и същи букви (напр. "listen" и "silent"). Решение: Сортираме и двата низа и сравняваме.

bool areAnagrams(string s1, string s2) {
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    return s1 == s2;
}

5.3. Обхождане (Reverse)

string s = "abc";
reverse(s.begin(), s.end()); // "cba"
// Изисква #include <algorithm>

---

6. StringStream

Полезен клас за "парстване" на низове, сякаш четем от конзолата.

#include <sstream>
// ...
string data = "Ivan 20 5.50";
stringstream ss(data);

string name;
int age;
double grade;

ss >> name >> age >> grade;
// name="Ivan", age=20, grade=5.50

---

7. Допълнителни операции с низове

7.1. Разделяне на низ (Tokenization)

Често се налага да разделите низ на думи или компоненти. Най-простият метод е чрез stringstream:

string text = "Apple Banana Cherry";
stringstream ss(text);
string word;

while (ss >> word) {
    cout << word << endl; // Apple, Banana, Cherry
}

За разделяне по специфичен разделител (напр. запетая):

string data = "Ivan,20,Sofia";
size_t pos = 0;
while ((pos = data.find(',')) != string::npos) {
    cout << data.substr(0, pos) << endl;
    data.erase(0, pos + 1);
}
cout << data << endl; // Последният елемент

7.2. Премахване на интервали (Trim)

Често входните данни съдържат водещи или завършващи интервали:

string trim(string s) {
    size_t start = s.find_first_not_of(" \t\n");
    size_t end = s.find_last_not_of(" \t\n");

    if (start == string::npos) return ""; // Празен низ
    return s.substr(start, end - start + 1);
}

7.3. Замяна на подниз (Replace)

string text = "Hello World";
size_t pos = text.find("World");
if (pos != string::npos) {
    text.replace(pos, 5, "C++"); // "Hello C++"
}

Или за заместване на всички срещания:

void replaceAll(string& str, const string& from, const string& to) {
    size_t pos = 0;
    while ((pos = str.find(from, pos)) != string::npos) {
        str.replace(pos, from.length(), to);
        pos += to.length();
    }
}

7.4. Проверка за префикс/суфикс

C++20 въведе starts_with и ends_with, но ако използвате по-стара версия:

bool startsWith(const string& str, const string& prefix) {
    return str.size() >= prefix.size() && 
           str.substr(0, prefix.size()) == prefix;
}

bool endsWith(const string& str, const string& suffix) {
    return str.size() >= suffix.size() && 
           str.substr(str.size() - suffix.size()) == suffix;
}

---

8. Сравнение на низове

8.1. Лексикографско сравнение

Операторът < сравнява низове лексикографски (словоредно):

string a = "apple", b = "banana";
if (a < b) cout << "Apple идва преди Banana"; // Вярно

За игнориране на регистъра (case-insensitive):

bool compareIgnoreCase(string a, string b) {
    transform(a.begin(), a.end(), a.begin(), ::tolower);
    transform(b.begin(), b.end(), b.begin(), ::tolower);
    return a == b;
}

---

9. Задачи за упражнение

1. CSES String Matching: Основно търсене на подниз.
2. Codeforces 71A: Way Too Long Words (манипулация на низове).
3. LeetCode 14: Longest Common Prefix.
4. UVa 10082: WERTYU (трансформация на символи).

---

🏁 Заключение

std::string е мощен инструмент за манипулация на текст. Овладяването на основни операции като find, substr, конвертиране и сравнение ще ви спести много време в състезания. За по-напреднали задачи (като KMP, Z-алгоритъм, суфиксни масиви), вижте Тема 36: Алгоритми върху низове.

Съвети: * Винаги проверявайте резултата от find за string::npos. * Внимавайте с индексите при substr и erase. * Използвайте stringstream за лесно парсване на данни.