In [1]:
#include <string>

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

A. Лексикографически меньше

Требуется сравнить две строки S1 и S2 лексикографически. Слово a лексикорафически меньше слова b (a < b), если первые m символов слов совпадают, а m+1 символ слова a меньше m+1 символа слова b или a является префиксом b. Строка a длины n является префиксом строки b длины m, если n < m и a0=b0, a1=b1 .... an=bn

Пример

входные данные

abcde

abd

выходные данные

<

Разбор задачи

Сравниваем символы строк 1-ый с 1-ым, 2-ой со 2-ым и так далее, пока мы не обнаружим первое несовпадение или пока одна из строк не закончится.

В первом случае (если мы нашли пару символов, которая не совпадает) сравниваем это символы. На основе этого сравнения определяем, которая строка лексикографически меньше.

Во втором случае одна из строк закончилась раньше другой и соответственно лексикографически меньшей считаем ту, чья длина меньше. Также возможен случай, когда длины строк равны и все пары символов совпадают. В этом случае нужно вывести ’=’.

In [2]:
{
	int i, k;
	string s;
	string s0;
	std::cin >> s;
	std::cin >> s0;
	k = min(s.length(), s0.length());
	for (i = 0; i < k && s[i] == s0[i]; i++);
	if (i < k)
	{
		if (s[i] < s0[i]) {
			cout << "<";
		}
		else {
			cout << ">";
		}
	}
	else {
		if (s.length() < s0.length())
			cout << "<";
		else {
			if (s.length() > s0.length())
				cout << ">";
			else
				cout << "=";
		}
	}
}
aabc
abc
<

B. Скобочная последовательность 1

Дана строка S состоящая из символов "(" и ")". Требуется выяснить, является ли эта строка правильной скобочной последовательностью.

Правильная скобочная последовательность определяется следующим образом:

  • Пустая строка есть правильная скобочная последовательность;

  • Пусть S — правильная скобочная последовательность, тогда (S) есть правильная скобочная последовательность;

  • Пусть S1, S2 — правильные скобочные последовательности, тогда S1S2 есть правильная скобочная последовательность;

Разбор задачи

В данной задаче заведём счётчик открывающихся скобок. В начале алгоритма counter = 0; Далее идём по строке слева-направо и просматриваем каждый символ строки. Если это открывающаяся скобка, то счётчик увеличиваем на 1. Если это закрывающаяся скобка, то уменьшаем счётчик на 1.

Наша последовательность является правильной тогда и только тогда, когда выполнены 2 условия:

  1. Ни в какой момент времени счётчик не был меньше нуля.
  2. По окончанию нашего алгоритма счётчик = 0.
In [3]:
{
	std::string s;
	std::cin >> s;
	int depth = 0;
	int i = 0;
	int n = (int)s.length();
	for (i = n - 1; i >= 0; --i) {
		if (s[i] == '(') {
			--depth;
		}
		else {
			++depth;
		}
		if (depth < 0) {
			depth = -1;
			break;
		}

	}
	if (depth == 0) {
		std::cout << "YES" << std::endl;
	}
	else {
		std::cout << "NO" << std::endl;
	}
}
()())
NO

C. Количество вхождений

Даны две строки S1 и S2. Посчитайте количество вхождений строки S1 в строку S2.

Разбор задачи

В данной задаче длины строк не велики, поэтому будем "прикладывать" меньшую строку к большей. Заметим, что начало вхождения меньшей строки в большей может начинаться с 1-ого, 2-ого ... length(s1) - length(s2) + 1 символа.

In [1]:
{
    std::string s1;
    std::string	s2;
    std::cin >> s1;
    std::cin >> s2;
    int k = 0;
    for (int i = 0; i < s2.length(); i++)
        if (s2.substr(i, s1.length()) == s1)
            k++;
    cout << k;
}
input_line_7:5:10: error: no member named 'cin' in namespace 'std'
    std::cin >> s1;
    ~~~~~^
input_line_7:6:10: error: no member named 'cin' in namespace 'std'
    std::cin >> s2;
    ~~~~~^
input_line_7:11:5: error: use of undeclared identifier 'cout'
    cout << k;
    ^
Interpreter Error: 

D. Строка

Дана строка S вида $p_1 c_1 p_2 c_2...p_n c_n$. Вам нужно составить строку L из $p_1$ символов $c_1$, $p_2$ символов $c_2$, и так далее.

Разбор задачи

Идем по строке, просматривая каждый символ. Если мы нашли такое место, что предыдущий символ не является цифрой (s[i-1] < ’0’ || s[i-1] > ’9’), а следующий является, то начинаем кон- струировать новое число. После того, как мы полностью построили очередное число, выводим столько символов после числа, какого его значение.

In [5]:
{
	std::string s1;
	std::string s;
	std::string temp;
	std::cin >> s1;
	for (int i = 0; i < s1.length(); i++)
	{	
		if (s1[i] >= '0' && s1[i] <= '9') {
			temp += s1[i];
		}
		else if (s1[i] < '0' || s1[i] > '9') {
			s.append(string(stoi(temp), s1[i]));
			temp.clear();
		}
	}
	cout << s;
}
2a4b3c
aabbbbccc

E. Скобочная последовательность 2

Дана строка S состоящая из символов "(", ")", "{", "}", "[" и "]". Требуется выяснить, является ли эта строка правильной скобочной последовательностью.

Разбор задачи

Эту задачу удобно решать моделированием. Заведём стек символов. Идём по строке, просматри вая символы. Если мы встретили открывающуюся скобку, то положим её в стек. Если мы встретили закрывающуюся скобку, то нам нужно достать из стека последний символ. При этом возможны 2 варианта:

  • Последний символ является открывающейся скобкой того же типа. В таком случае мы извле каем её из стека (ничего нового в стек не добавляем). Переходим к следующему символу строки.

  • Последний символ не является открывающейся скобкой того же типа. В таком случае данная нам последовательность не является правильной скобочной последовательностью. Можно закончить алгоритм.

После того, как мы достигли конца строки стек должен быть пуст. Если это не верно, то данная нам последовательность не является правильной скобочной последовательностью.

In [6]:
{
    string s1;
    stack <char> st;
    cin >> s1;
    for (auto a : s1){
        if (a == '(' || a == '[' || a == '{')
            st.push(a);
        if (a == ')' || a == ']' || a == '}'){
            if (st.empty()) {
                cout << "NO";
                break;
            }
            
            if (st.top() == a - 1 || st.top() == a - 2)
                st.pop();
            else {
                cout << "NO";
                break;
            }
        }
    }
    if (st.empty())
        cout << "YES";
    else
        cout << "NO";
}
([{}])
YES

F. Максимальный палиндром

Дана строка S, состоящая из строчных латинских букв. Требуется найти самую длинную подстроку строки S, являющуюся палиндромом. Строка L является палиндромом, если L1 = Ln, L2 = Ln - 1, ..., . Например, строки abba, abacaba, abdba, aaaaa, a – являются палиндромами, а строки abc, cca – не являются.

Разбор задачи

У каждого палиндрома есть середина.

Серединой может являться символ или граница двух символов. В любом случае мы можем рассмотреть все возможные середины палиндромов.

То есть, идём по строке, просматривая символы. Пусть символ s[i] является серединой некоторого палиндро- ма. Далее найдем длину максимального палиндрома, серединой которого он является.

В худшем случае его длина будет = 1 (палиндром состоит из одного символа s[i]). Для того, чтобы найти длину максимального палиндрома, серединой которого является символ s[i] будем сравнивать па- ры символов слева и справа от s[i]. На первом шаге сравним s[i-1] и s[i+1].

Далее сравним s[i-2] и s[i+2] и так далее, пока мы не найдем первые 2 несовпадающих символа.

In [7]:
{
	int n, ans = 1, pos = 0;
	std::string	s;
	std::cin >> s;
	n = s.length();

	vector<int> d1(n);
	int l = 0, r = -1;
	for (int i = 0; i < n; ++i) {
		int k = (i > r ? 0 : min(d1[l + r - i], r - i)) + 1;
		while (i + k < n && i - k >= 0 && s[i + k] == s[i - k])  ++k;
		d1[i] = k--;
		if (i + k > r)
			l = i - k, r = i + k;
		if (2 * d1[i] - 1 > ans)
			ans = 2 * d1[i] - 1, pos = i;
	}

	vector<int> d2(n);
	l = 0, r = -1;
	for (int i = 0; i < n; ++i) {
		int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1)) + 1;
		while (i + k - 1 < n && i - k >= 0 && s[i + k - 1] == s[i - k])  ++k;
		d2[i] = --k;
		if (i + k - 1 > r)
			l = i - k, r = i + k - 1;
		if (2 * d2[i] > ans)
			ans = 2 * d2[i], pos = i;
	}


	cout << ans << endl;
	if (ans % 2 == 1)
	{
		ans /= 2;
		for (int i = pos - ans; i <= pos + ans; i++)
			printf("%c", s[i]);
	}
	else
	{
		ans /= 2;
		for (int i = pos - ans; i < pos + ans; i++)
			printf("%c", s[i]);
	}

}
abc
1

G. Сравни подстроки

На вход подаётся строка. Требуется сравнить пару её подстрок лексикографически.

Входные данные

В первой строке находится строка, состоящая из строчных латинских символов алфавита. Длина строки 1 ≤ n ≤ 10^6. Во второй строке содержится число m – количество запросов, 1 ≤ m ≤ 105. Следующие m строк содержат по 4 числа – индексы начала и конца первой подстроки и индексы начала и конца второй подстроки. Длины подстрок > 0.

Разбор задачи

Решение аналогично задачи: A. Лексикографически меньше

In [8]:
std::vector<long long> P, H;
int a = 29, mod = 1e9 + 7;
In [9]:
int64_t hsh(int l, int r)
{
	if (l == 0)
		return H[r];
	return ((H[r] - (H[l - 1] * P[r - l + 1]) % mod) + mod) % mod;
}
In [ ]:
{
	string S, s;
	cin >> S;
	int n = S.size();
	H.resize(n);
	P.resize(n);
	H[0] = (S[0] - 'a' + 1);
	P[0] = 1;
	for (int i = 1; i < n; i++)
	{
		P[i] = (P[i - 1] * a) % mod;
		H[i] = ((H[i - 1] * a) % mod + S[i] - 'a' + 1) % mod;
	}
	int m;
	cin >> m;
	int l, r, l1, r1, l2, r2;
	for (int i = 0; i < m; i++)
	{
		cin >> l1 >> r1 >> l2 >> r2;
		l = -1;
		r = min(r1 - l1, r2 - l2) + 1;
		int m;
		bool b = true;
		while (r - l > 1)
		{
			m = (r + l) / 2;
			if (hsh(l1, l1 + m) == hsh(l2, l2 + m))
				l = m;
			else
			{
				r = m;
				b = false;
			}
		}
		if (b)
		{
			if (r1 - l1 == r2 - l2)
				cout << "=\n";
			else if (r1 - l1 > r2 - l2)
				cout << ">\n";
			else
				cout << "<\n";
		}
		else
		{
			if (S[l1 + r] > S[l2 + r])
				cout << ">\n";
			else
				cout << "<\n";
		}
	}
}
abcabc
1
abc

H. Подстрока в строке

Вам дается 2 строки, состоящие только из строчных латинских символов. Вам нужно найти все позиции, где вторая строка может быть найдена в первой строке.

Разбор задачи

Ищем вторую строку в первой строке через find, пока не достигли конца строки, запоминая количество совпадений и позиции через npos.

In [11]:
{
	string s;
	string s0;
	std::cin >> s;
	std::cin >> s0;
	string print;
	int count = 0;
	int i = 0;
	for (i = s.find(s0, i++); i != string::npos; i = s.find(s0, i + 1)) {
		count++;
		print.append(to_string(i) + " ");
	}
	cout << count << endl;
	cout << print << endl;
}
abcabcabc
abc
3
0 3 6 

I. Различные подстроки

Дана строка. Сколько различных подстрок, не считая пустой, она содержит?

Разбор задачи

Используем алгоритм LCP (Алгоритм Касаи).

Будем сортировать циклические сдвиги строки s; если считать, что символ $ лексикографически меньше любого другого символа, то порядок сортировки будет таким же, что и порядок сортировки суффиксов.

Будем сортировать циклические сдвиги строки s; если считать, что символ $ лексикографически меньше любого другого символа, то порядок сортировки будет таким же, что и порядок сортировки суффиксов.

Алгоритм будет состоять из нескольких шагов.

После k-ого шага алгоритм будет получать лексикографический порядок для подстрок циклической строки s = s + s + . . ., имеющих длину 2^k и начинающихся в позициях 0, . . . , |s| − 1.

Помимо лексикографического порядка подстрок, алгоритм будет поддерживать информацию о классах эквивалентности этих подстрок. В классе эквивалентности лежат все попарно равные подстроки текущей длины; классы эквивалентности можно упорядочить лексикографически и пронумеровать в этом же порядке.

Для каждой подстроки алгоритм также будет поддерживать номер ее класса эквивалентности при лексикографическом упорядочивании (теперь результат лексикографического сравнения подстрок совпадает с результатом сравнения номеров соответствующих классов).

Итоговое время составляет O(|s|log2 |s|), либо O(|s| log |s|).

Подробнее:

In [12]:
#define MAXN 65536
#define MAXLG 17
In [13]:
struct entry { int nr[2], p; } L[MAXN];
In [14]:
int Pi[MAXLG][MAXN], N, i, stp, cnt;
In [15]:
int cmp(struct entry a, struct entry b)
{
	return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
}
In [16]:
int compute_lcp(int x, int y)
{
	int k, ret = 0;
	if (x == y) return N - x;
	for (k = stp - 1; k >= 0 && x < N && y < N; k--)
	{
		if (Pi[k][x] == Pi[k][y]) { x += 1 << k; y += 1 << k; ret += 1 << k; }
	}
	return ret;
}
In [17]:
{
	std::string A;
	std::cin >> A;
	for (N = A.length(), i = 0; i < N; i++) Pi[0][i] = A[i] - 'a';
	for (stp = 1, cnt = 1; cnt >> 1 < N; stp++, cnt <<= 1)
	{
		for (i = 0; i < N; i++)
		{
			L[i].nr[0] = Pi[stp - 1][i];
			L[i].nr[1] = i + cnt < N ? Pi[stp - 1][i + cnt] : -1;
			L[i].p = i;
		}
		sort(L, L + N, cmp);
		for (i = 0; i < N; i++) Pi[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? Pi[stp][L[i - 1].p] : i;
	}

	int *sa = new int[N];
	for (i = 0; i < N; i++) sa[Pi[stp - 1][i]] = i;

	int *lcp = new int[N];
	for (i = 0; i < N - 1; i++) { lcp[i] = compute_lcp(sa[i], sa[i + 1]); }

	int res = N - sa[0];
	for (i = 1; i < N; i++)    res += N - sa[i] - lcp[i - 1];

	cout << res << endl;

}
abcdefg
28