e-olymp 8570. Длина слов

10/03/2019 by Иван Киреев

Задача. Длина слов

Задан текст — последовательность слов. Найдите длину каждого слова.

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

Текст содержит последовательность слов. Длина каждого слова не более $20$.

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

Для каждого слова в одной строке выведите его длину.

Тесты

№	Ввод	Вывод
1	Programming Principles 1	11 10 1
2	I like C very much	1 4 1 4 4
3	12345678901234567890	20
4	;-\ <cstring>	3 9
5	5^2-7*4/2 = 11	9 1 2
6	Veeeeeeery bIg LeTteR!	10 3 7
7	1, 25. 10!	2 3 3

Решение

Считываем в потоке и выводим длину каждого слова через пробел.

Код через строки string

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string str;
    while (cin >> str) cout << str.length() << ' ';
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string str;

while (cin >> str) cout << str.length() << ' ';

return 0;

}

Код через строки c-string

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char str[20];
    while (cin >> str) cout << strlen(str) << ' ';
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char str[20];

while (cin >> str) cout << strlen(str) << ' ';

return 0;

}

Related Images:

e-olymp 4844. Поиск общей подстроки

24/02/2019 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m [/latex]. Также дано число [latex] L [/latex].

Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].

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

В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L (0 \leq L \leq 100000) [/latex] — длина общей подстроки.

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

В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].

Тесты

#	Входные данные	Выходные данные
1	saaa baaa 3	YES
2	raabc taaac 3	NO
3	aaaaaaaka akaa 3	YES
4	abcdfeg qwertycdfeg 10	NO

Код 1

#include <iostream>
#include <map>
using namespace std;
 
struct state {
    int len, link;
    map <char,int> next;
};
 
state st[2*100000]; 
int sz, last;
 
void sa_init() {
    sz = 0;
    last = 0;
    st[0].len = 0;
    st[0].link = -1;
    sz++;
}
 
void sa_extend (char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
    if (p == -1) st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
 
int longest_common_string (string a, string b) {
    sa_init();
    for (int i = 0; i < a.length(); i++) sa_extend (a[i]);
    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < b.length(); i++) {
        while (v != 0 && ! st[v].next.count(b[i])) {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(b[i])) {
            v = st[v].next[b[i]];
            l++;
        }
        if (l > best){
            best = l;
            bestpos = i;
        }
    }
    return best;
}
 
int main() {
    string a, b;
    int n;
    cin >> a >> b >> n;
    if (longest_common_string(a, b) >= n) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

struct state {

int len, link;

map <char,int> next;

};

state st[2*100000];

int sz, last;

void sa_init() {

sz = 0;

last = 0;

st[0].len = 0;

st[0].link = -1;

sz++;

}

void sa_extend (char c) {

int cur = sz++;

st[cur].len = st[last].len + 1;

int p;

for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;

if (p == -1) st[cur].link = 0;

else {

int q = st[p].next[c];

if (st[p].len + 1 == st[q].len) st[cur].link = q;

else {

int clone = sz++;

st[clone].len = st[p].len + 1;

st[clone].next = st[q].next;

st[clone].link = st[q].link;

st[q].link = st[cur].link = clone;

}

last = cur;

}

int longest_common_string (string a, string b) {

sa_init();

for (int i = 0; i < a.length(); i++) sa_extend (a[i]);

int v = 0, l = 0, best = 0, bestpos = 0;

for (int i = 0; i < b.length(); i++) {

while (v != 0 && ! st[v].next.count(b[i])) {

v = st[v].link;

l = st[v].len;

}

if (st[v].next.count(b[i])) {

v = st[v].next[b[i]];

l++;

}

if (l > best){

best = l;

bestpos = i;

}

return best;

}

int main() {

string a, b;

int n;

cin >> a >> b >> n;

if (longest_common_string(a, b) >= n) cout << "YES";

else cout << "NO";

return 0;

}

Решение 1

Суффиксный автомат

Создадим структуру struct state, которая будет хранить информацию о переходах. len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии), link — это суффиксальная ссылка, список переходов будем хранить в контейнере map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные last и sz, отвечающие за последнее состояние и номер нового состояния соответственно.

Нам потребуется функция инициализирующая суффиксный автомат sa_init(). Так как вначале состояние лишь одно, то его длина равна [latex]0[/latex], а суффиксную ссылку приравняем к [latex]-1[/latex].

В автомат будем добавлять символы поочередно, для чего нам потребуется еще одна функция sa_extend(). В начале которой будем присваивать новому состоянию соответствующий номер. А затем будем просматривать все переходы из последнего состояния по текущему символу. Таким образом переход либо будет, либо нет. Если его нет, то добавим его в текущее состояние cur и продолжим смотреть дальше, если же при этом мы дошли до состояния, на которое указывает суффиксная ссылка изначального состояния (нулевого), то суффиксную ссылку текущего состояния приравняем к нулю. Далее рассматриваем случай, когда из текущего состояния по символу переход существует, обозначим q за состояние, куда ведет переход.

Поиск наибольшей общей подстроки

Сначала для строки a построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние v и переменная, отвечающая за длину совпадающей части l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки bestpos — это максимум из всех значений l.

Код 2

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char a[100001], b[100001]; 
    int l1, l2, l, k = 0;
    cin >> a >> b >> l;
    l1 = strlen(a);
    l2 = strlen(b);
    if (l1 < l || l2 < l) cout << "NO";
    else {
        for (int i = 0; i < l1; i ++) {
            for (int j = i; j <= l ; j ++) {
                if (a[j] == b[j]) k ++;
                else i ++;
                if (k == l) {
                    cout << "YES";
                    return 0;
                }
            }
            k = 0;
        }
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char a[100001], b[100001];

int l1, l2, l, k = 0;

cin >> a >> b >> l;

l1 = strlen(a);

l2 = strlen(b);

if (l1 < l || l2 < l) cout << "NO";

else {

for (int i = 0; i < l1; i ++) {

for (int j = i; j <= l ; j ++) {

if (a[j] == b[j]) k ++;

else i ++;

if (k == l) {

cout << "YES";

return 0;

}

k = 0;

}

cout << "NO";

}

return 0;

}

Решение 2

Стоит отметить сразу, что данный код, по сути не работает на некоторых тестах, например когда символы, которые должны входить в искомую наибольшую подстроку, стоят в начале или конце обоих строк или хотя бы одной из них. Однако, как показывает практика, тесты на e-olymp данный способ посимвольного сравнения проходит. В данном варианте решения будем использовать c-string. Сами строки объявлены так: char a[100001], b[100001];, где [latex]100001[/latex] — это максимальная длина строки, которая может быть по условию задачи, и еще [latex]+1[/latex]. Объявить можно было еще и так: char * a = new char [100001];

Ссылки

Related Images:

e-olymp 3912. Реверс удавов

20/04/2018 by Мороз Дима

Задача

На каждом удаве из стаи написано его имя. Имя удава написано маленькими латинскими буквами от головы к хвосту. Все удавы из стаи ползут друг за другом, ведь так легче ползти. Иногда вожак даёт команду «Реверс». В этом случае каждый удав стаи разворачивается, и стая начинает ползти в противоположном направлении. Название стаи можно прочитать, если читать от головы удава, ползущего первым, к хвосту последнего. При этом название может измениться после команды «Реверс». Имена же удавов не меняются.

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

Первая строка содержит одно число $N (1 ≤ N ≤ 100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные	Выходные данные
3 abc def ghi	ghidefabc
3 zxcgh i db	dbizxcgh
4 mn kjl iu ghj	ghjiukjlmn
8 kdh jg lqwoc kfxvk iduhx nsh s kjwyv	kjwyvsnshiduhxkfxvklqwocjgkdh

Код программы (string)

#include <iostream>
#include <string.h>
using namespace std;

int main () 
{
    int N;
    cin >> N;
    string flock[N];
    for (int i = 0; i < N; i++)
        cin >> flock[i];
    for (int i = N - 1; i >= 0; i--)
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main ()

{

int N;

cin >> N;

string flock[N];

for (int i = 0; i < N; i++)

cin >> flock[i];

for (int i = N - 1; i >= 0; i--)

cout << flock[i];

return 0;

}

Решение задачи (string)

Записываем каждого удава в одномерный массив flock типа string размера N, а затем выводим его, начиная с конца.

Код программы (c-string)

#include <iostream>
#include <cstring>
using namespace std;

#define boa_name_size 11

int main() 
{
    int N;
    cin >> N;
    char **flock = new char *[N]; // Создаем массив в N строк
    for (int i = 0; i <= N; i++)
        flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов
    for (int i = 0; i <= N; i++)
        cin.getline(flock[i], boa_name_size);
    for (int i = N; i > 0; i--) 
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

#define boa_name_size 11

int main()

{

int N;

cin >> N;

char **flock = new char *[N]; // Создаем массив в N строк

for (int i = 0; i <= N; i++)

flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов

for (int i = 0; i <= N; i++)

cin.getline(flock[i], boa_name_size);

for (int i = N; i > 0; i--)

cout << flock[i];

return 0;

}

Решение задачи (c-string)

Записываем каждого удава в динамический массив flock типа char размера $N$ $\times$ boa_name_size, где boa_name_size – это константа, размером в $11$ символов, которую определяем с помощью директивы #define в начале программы. Не $10$, а $11$ потому что в нуль-терминированных строках (c-string) последний символ – символ конца строки '\0'.
Далее выводим наш массив с последней строки до первой.