e-olymp 9407. Слияние строк

18/12/2019 by Даниил Кулык

Задача

Имеются две строки $A$ и $B$.

Ваша задача — найти такую строку $C$, которая содержит в себе и $A$ и $B$ в качестве подстрок и является кратчайшей среди всех таких возможных строк.

Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка $kbtu$ является подстрокой строки $kbtu open$, но строка $fall$ подстрокой не является.

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

Первая строка содержит строку $A$ $(1 \leqslant |A| \leqslant 10^5)$.

Вторая строка содержит строку $B$ $(1 \leqslant |B| \leqslant 10^5)$.

Гарантируется, что обе строки содержат только строчные латинские буквы.

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

Выведите одну строку $C$.

Тесты

№	Входные данные	Выходные данные
1.	compressing single	compressingle
2.	can you	canyou
3.	compressiondoneright doner	compressiondoneright
4.	details tail	details
5.	essential code	essentialcode

Код

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

int main() 
{
    int n, m, z;
    string a, b, c, d;
    cin>>a; // Вводим строку A
    cin>>b; // Вводим строку B
    d = b; // Строку B будем хранить в переменной d
    n = b.length(); // В переменной n храним длину строки B
    m = a.length(); // В переменной m храним длину строки A
    c = a.substr(m - n, n); // Создаём подстроку
    if(a.find(b) == EOF) // Ищем в строке A строку B
    {
        for (int i = 1; i<=n && b != c; i++) // Удаляем символы в конце первой строки и начале второй, пока они не будут равны
        {
            b.erase(n - i,1);  
            c.erase(0, 1);
        }
        z = c.length(); // В переменной z храним длину подстроки
        d.erase(0,z); // Удаляем из строки B элементы подстроки
        cout << a + d; // Выводим такую строку, которая содержит в себе и A и B
    }
    else cout << a; // Выводим строку A
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int n, m, z;

string a, b, c, d;

cin>>a; // Вводим строку A

cin>>b; // Вводим строку B

d = b; // Строку B будем хранить в переменной d

n = b.length(); // В переменной n храним длину строки B

m = a.length(); // В переменной m храним длину строки A

c = a.substr(m - n, n); // Создаём подстроку

if(a.find(b) == EOF) // Ищем в строке A строку B

{

for (int i = 1; i<=n && b != c; i++) // Удаляем символы в конце первой строки и начале второй, пока они не будут равны

{

b.erase(n - i,1);

c.erase(0, 1);

}

z = c.length(); // В переменной z храним длину подстроки

d.erase(0,z); // Удаляем из строки B элементы подстроки

cout << a + d; // Выводим такую строку, которая содержит в себе и A и B

}

else cout << a; // Выводим строку A

return 0;

}

Решение

В данной задаче необходимо создать строку $C$, которая будет содержать в себе строки $A$ и $B$. Рассмотрим два варианта решения задачи. Первый – если строка $B$ полностью содержится в строке $A$, то выводим строку $A$. Второй – если строка $B$ содержится в $A$ частично или не содержится вообще, выводим строку $A$ $+$ элементы строки $B$, которых нет в $A$.

Для проверки, находится ли строка $B$ в $A$, воспользуемся функцией find(). Если попадаем в первый вариант решения задачи, то выводим $A$. Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$, и на выход подаём строку $C$, которая состоит из строки $A$ и оставшихся элементов строки $B$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

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 4843. Равные подстроки

26/12/2018 by Юлиана Боурош

Задача

Дана строка $S = s_1 s_2 s_3\cdots s_n$и множество запросов вида $(l_1, r_1, l_2, r_2)$.

Для каждого запроса требуется ответить, равны ли подстроки $s_{l1} … s_{r1}$ и $s_{l2} \cdots s_{r2}$.

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

В первой строке записана строка $S$, состоящая из строчных латинских букв. Эта строка непустая и имеет длину не более $100000$ символов. Во второй строке записано целое число $q (1 \leq q \leq 50000)$ — количество запросов. В каждой из следующих $q$ строк записаны числа $l_1, r_1, l_2, r_2 (1\leq l_1 \leq r_1 \leq |S|; 1\leq l_2 \leq r_2 \leq |S|)$.

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

Для каждого запроса выведите «$+$», если соответствующие подстроки равны, и «$-$», в противном случае.

Тесты

№	Входные данные	Выходные данные
1	abacaba 4 1 1 7 7 1 3 5 7 3 4 4 5 1 7 1 7	++-+
2	qa 3 1 1 1 1 2 2 2 2 1 1 2 2	++-
3	barcarbank 3 2 3 5 6 1 2 7 8 1 3 7 9	++-
4	abbabdad 4 1 3 4 6 2 3 5 6 1 2 4 5 3 5 6 8	—++

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

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

int main() {
    string s;
    int q, begin1, end1, begin2, end2;
    getline(cin, s);
    cin >> q;
    while (q--) {
        cin >> begin1 >> end1 >> begin2 >> end2;
        end1 -= --begin1; // в begin1/2 останется индекс начала подстроки
        end2 -= --begin2; // в end1/2 - кол-во последующих букв
        cout << (s.substr(begin1, end1) == s.substr(begin2, end2) ? '+' : '-'); 
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

int q, begin1, end1, begin2, end2;

getline(cin, s);

cin >> q;

while (q--) {

cin >> begin1 >> end1 >> begin2 >> end2;

end1 -= --begin1; // в begin1/2 останется индекс начала подстроки

end2 -= --begin2; // в end1/2 - кол-во последующих букв

cout << (s.substr(begin1, end1) == s.substr(begin2, end2) ? '+' : '-');

}

return 0;

}

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

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

int main() {
    char str[100001], substr1[100001], substr2[100001];
    cin >> str;
    int q, l1, r1, l2, r2;
    cin >> q;
    while (q--) {
        cin >> l1 >> r1 >> l2 >> r2;
        strncpy(substr1, &str[l1 - 1], r1 - l1 + 1);
        strncpy(substr2, &str[l2 - 1], r2 - l2 + 1);
        cout <<( strcmp(substr1,substr2) == 0 ? '+': '-');
        memset(substr1, 0, sizeof(substr1)/sizeof(substr1[0]));
        memset(substr2, 0, sizeof(substr2)/sizeof(substr2[0]));
        
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char str[100001], substr1[100001], substr2[100001];

cin >> str;

int q, l1, r1, l2, r2;

cin >> q;

while (q--) {

cin >> l1 >> r1 >> l2 >> r2;

strncpy(substr1, &str[l1 - 1], r1 - l1 + 1);

strncpy(substr2, &str[l2 - 1], r2 - l2 + 1);

cout <<( strcmp(substr1,substr2) == 0 ? '+': '-');

memset(substr1, 0, sizeof(substr1)/sizeof(substr1[0]));

memset(substr2, 0, sizeof(substr2)/sizeof(substr2[0]));

}

return 0;

}

Решение

Циклично находим указанные подстроки на введённых отрезках символов и сравниваем их.

Ссылки

string

c-string

Related Images:

e-olymp 1611. Реверс подстроки

26/06/2018 by Карина Миловская

Задача

Дана строка $s$, в которой выделили подстроку, состоящую из символов с $i$-го по $j$-ый включительно (символы строки $s$ нумеруются с единицы) и поменяли местами $i$-ый символ с $j%-ым, %(i + 1)%-ый с %(j — 1)$-ым и так далее (конвертировали подстроку). Выведите строку $s$ после внесенных изменений.

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

В первой строке содержится строка $s$ длиной не более $1000$ символов, во второй — два числа $i$ и $j$ $\left (i \leqslant j \right).$

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

Выведите строку $s$ после внесенных изменений.

Тесты

Входные данные	Выходные данные
$zbbg \\ 2 \; 3$	$zbbg$
$gaqipkajibk \\ 5 \; 6$	$gaqikpajibk$
$helloworld \\ 5 \; 7 $	$helloworld$
$rkdobnjfyy \\ 6 \; 3 $	$rkdobnjfyy$

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

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

int main() {
    char s[1001];
    cin >> s;
    int i, j;
    cin >> i >> j;
    for (int b = i - 1, c = j - 1; b < c; b++,c--) {
        int k = s[b];
        s[b] = s[c];
        s[c] = k;
    }
    cout << s;
    
    return 0;
    
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[1001];

cin >> s;

int i, j;

cin >> i >> j;

for (int b = i - 1, c = j - 1; b < c; b++,c--) {

int k = s[b];

s[b] = s[c];

s[c] = k;

}

cout << s;

return 0;

}

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

Для решения задачи объявим массив, в котором будем хранить входную строку. Далее в цикле обращаем подстроку и выводим строку $s$ после внесенных изменений.

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

#include <iostream>
using namespace std;
 
int main() {
    string s;
    cin >> s;
    int i, j;
    cin >> i >> j;
    for (int b = i - 1, c = j - 1; b < c; b++,c--) {
        int k = s[b];
        s[b] = s[c];
        s[c] = k;
 
    }
    cout << s;
 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

int i, j;

cin >> i >> j;

for (int b = i - 1, c = j - 1; b < c; b++,c--) {

int k = s[b];

s[b] = s[c];

s[c] = k;

}

cout << s;

return 0;

}

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

Для решения задачи вводим строку $s$. Далее в цикле конвертируем подстроку и выводим строку $s$ после внесенных изменений.

Ссылки

Условие задачи на e-olymp
Код решения на ideone(c-string)
Код решения на ideone(string)

Related Images:

e-olymp 2197. Антипалиндром

10/12/2017 by Сытников Дан

Антипалиндром

Условие задачи:

Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите её наибольшую по длине подстроку, не являющуюся палиндромом.

Входные данные
Входной файл содержит строку s. Она состоит только из строчных букв латинского алфавита, не пуста, её длина не превышает 100000 символов.

Выходные данные
В выходной файл выведите ответ на задачу, если ответов несколько — выберите лексикографически минимальный. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Тесты

№	Входные данные	Выходные данные
1	abba	abb
2	aaaaaaa	NO SOLUTION
3	abcghgcba	abcghgcb
4	abaaabbb	abaaabbb

Код на языке C++:

#include <iostream>
using namespace std;

bool eqchar(string s) {     // Проверка, является ли строка множеством одинаковых символов
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != s[0]) return false;
    }
    return true;
}

bool ispal(string s) {      // Проверка, является ли строка палиндромом
    for (int i = 0; i < s.length()/2; i++) {
        if (s[i] != s[s.length() - i - 1])  return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    if (eqchar(s)) cout << "NO SOLUTION";
    else {
        if (!ispal(s))  cout << s;
        else {
            if (s[0] < s[1]) cout << s.substr(0, s.length() - 1);
            else cout << s.substr(1, s.length());
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

bool eqchar(string s) { // Проверка, является ли строка множеством одинаковых символов

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

if (s[i] != s[0]) return false;

}

return true;

}

bool ispal(string s) { // Проверка, является ли строка палиндромом

for (int i = 0; i < s.length()/2; i++) {

if (s[i] != s[s.length() - i - 1]) return false;

}

return true;

}

int main() {

string s;

cin >> s;

if (eqchar(s)) cout << "NO SOLUTION";

else {

if (!ispal(s)) cout << s;

else {

if (s[0] < s[1]) cout << s.substr(0, s.length() - 1);

else cout << s.substr(1, s.length());

}

return 0;

}

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static boolean eqchar(String s) {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(0)) return false;
        }
        return true;
    }

    public static boolean ispal(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;
        }
        return true;
    }

    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        String s = in .nextLine();
        if (eqchar(s)) System.out.println("NO SOLUTION");
        else {
            if (!ispal(s)) System.out.println(s);
            else {
                if (s.charAt(0) < s.charAt(1)) System.out.println(s.substring(0, s.length() - 1));
                else System.out.println(s.substring(1));
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static boolean eqchar(String s) {

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) != s.charAt(0)) return false;

}

return true;

}

public static boolean ispal(String s) {

for (int i = 0; i < s.length() / 2; i++) {

if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;

}

return true;

}

public static void main(String[] args) throws java.lang.Exception {

Scanner in = new Scanner(System.in);

String s = in .nextLine();

if (eqchar(s)) System.out.println("NO SOLUTION");

else {

if (!ispal(s)) System.out.println(s);

else {

if (s.charAt(0) < s.charAt(1)) System.out.println(s.substring(0, s.length() - 1));

else System.out.println(s.substring(1));

}

Решение задачи:
Сперва необходимо проверить, является ли строка множеством одинаковых символов. В этом случае найти подстроку, не являющуюся палиндромом, не представляется возможным. Затем проверим, является ли входная строка палиндромом. Если нет, выведем исходную строку. Иначе необходимо вывести подстроку без первого или последнего символа (в зависимости от лексикографического порядка строки).

Условие задачи на e-olymp
Засчитанная задача на e-olymp: на языке C++
Засчитанная задача на e-olymp: на языке Java
Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

e-olymp 1078. Степень строки

11/05/2017 by Вадим Гордийчук

Задача

Обозначим через [latex]a \cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a =[/latex]«abc» и [latex]b =[/latex]«def» то [latex]a \cdot b =[/latex]«abcdef».

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0} =[/latex]«» (пустая строка)
[latex]a^{n+1} = a \cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s = a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные	Выходные данные
abcabc gcdgcd gcgcgc gggggg hhhh	2 2 3 6 4
BbbbBbbbBbbb dogdogdog aaaaaaaa cstring	3 3 8 1

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

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

unsigned int cstringpow(const char *s)
{
    unsigned int answer = 1;
    const unsigned int size = strlen(s);
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (strncmp(s+j, s+j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    char s[1000010]; //Выделяем память для строк
    while (cin >> s)
        cout << cstringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned int cstringpow(const char *s)

{

unsigned int answer = 1;

const unsigned int size = strlen(s);

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (strncmp(s+j, s+j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

char s[1000010]; //Выделяем память для строк

while (cin >> s)

cout << cstringpow(s) << endl;

return 0;

}

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

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

Для решения поставленной задачи используем функцию cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной size (с использованием счётчика i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией strlen. Числа, которые будут получатся из выражения size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].

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

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

unsigned int stringpow(const string &s)
{
    unsigned int answer = 1;
    const unsigned int size = s.size();
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (s.compare(j, i, s, j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    string s; //Выделяем переменную класса "строка"
    while (cin >> s)
        cout << stringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

unsigned int stringpow(const string &s)

{

unsigned int answer = 1;

const unsigned int size = s.size();

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (s.compare(j, i, s, j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

string s; //Выделяем переменную класса "строка"

while (cin >> s)

cout << stringpow(s) << endl;

return 0;

}

import java.util.*;
import java.io.*;

public class Main
{
    public static int stringpow(String s)
    {
        int answer = 1;
        int size = s.length();
        for(int i = 1; i < size/2+1; ++i)
        {
            /*
            Ищем предполагаемую степень для ответа, которая
            обязательно является делителем длины строки.
            */
            if (size % i == 0)
            {
                boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна
                String current = s.substring(0, i);
                for(int j = 0; j < size-i; j += i)
                {
                    //сравниваем блоки строки
                    if (!(current.equals(s.substring(j+i, j+2*i))))
                    {
                        not_broken = false;
                        break;
                    }
                }
            
                if (not_broken)
                {
                    answer = size/i;
                    break;
                }
            }
        }
        return answer;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        String S; //Выделяем переменную класса "строка"
        while(in.hasNextLine())
        {
            S = in.nextLine();
            out.println(stringpow(S));
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

public class Main

{

public static int stringpow(String s)

{

int answer = 1;

int size = s.length();

for(int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна

String current = s.substring(0, i);

for(int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (!(current.equals(s.substring(j+i, j+2*i))))

{

not_broken = false;

break;

}

if (not_broken)

{

answer = size/i;

break;

}

return answer;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

String S; //Выделяем переменную класса "строка"

while(in.hasNextLine())

{

S = in.nextLine();

out.println(stringpow(S));

}

out.flush();

}

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

Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.

Ссылки

Related Images:

e-olymp 2171. Поиск набора образцов

19/05/2016 by Женя Максимова

Задача. Напишите программу, которая для каждой строки из заданного набора [latex]S[/latex] проверяет, верно ли, что она содержит как подстроку одну из строк из набора [latex]T[/latex].

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

Первая строка содержит натуральное число [latex]n (n\leq100)[/latex] — количество строк в наборе [latex]T[/latex]. Каждая из следующих [latex]n[/latex] строк содержит непустую строку длины не более [latex]80[/latex]-ти символов.

Оставшаяся часть файла содержит строки из набора [latex]S[/latex]. Каждая строка состоит из ASCII символов с кодами от [latex]32[/latex] до [latex]126[/latex] включительно. Строка может быть пустой; гарантируется, что длины строк не превышают [latex]250[/latex]-ти символов.

Гарантируется, что размер входного файла не превышает [latex]1[/latex] Мбайт.

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

Выведите все строки из набора [latex]S[/latex] (в том порядке, в котором они находятся во входном файле), содержащие как подстроку по крайней мере одну строку из набора [latex]T[/latex].

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

Тесты

Test	Input	Output
1	3 gr sud abc lksh sudislavl kostroma summer group b	sudislavl group b
2	4 a b + + xxx ababa dfs c + + qwerty xxxx	ababa c + + xxxx
3	1 a a b a c a d	a a a
4	2 bab aba aabba w w w

Код программы

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

#define in_range(x,y,z) for (int x=y; x<z; x++)
typedef long long ll;

int find_subctr(string t, string s)
{
  const int p = 97;  // основание системы счисления для хеширования строк
  // вычисляем степени числа P, чтобы ускорить процесс хеширования
  vector<ll> p_pow (s.length());
  p_pow[0] = 1;
  for (size_t i=1; i<p_pow.size(); ++i)
    p_pow[i] = p_pow[i-1] * p;
  // вычисляем хеши всех префиксов строки S
  vector<ll> h (s.length());
  for (size_t i=0; i<s.length(); ++i)
    {
      h[i] = (s[i] - 't' + 1) * p_pow[i];
      if (i)  h[i] += h[i-1];
    }
  // посчитаем хеш строки Т
  ll h_t = 0;
  for (size_t i=0; i<t.length(); ++i)
    h_t += (t[i] - 't' + 1) * p_pow[i];
  // сравниваем хеши строки T и подстрок S длины |T|
  for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)
    {
      ll cur_h = h[i+t.length()-1];
      if (i)  cur_h -= h[i-1];
      // если равенство выполняется хотя бы один раз, мы прекращаем поиск
      if (cur_h == h_t * p_pow[i])
        return int(i);
    }
  return -1;
}

int main()
{
  vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C
  int n;
  cin >> n;
  string tmp;
  getline(cin,tmp);
  in_range(i,0,n)
    {
      getline(cin,tmp);
      if(tmp.length()==1) C.push_back(tmp);
      T.push_back(tmp);
    }
  while(getline(cin,tmp))
    {
      S.push_back(tmp);
    }
  in_range(i,0,S.size())
    {
      string s=S[i];
      if(s=="") continue; // отсекаем случай пустой строки
      if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором
        {
          in_range(j,0,C.size())
          {
            string c=C[j];
            if(s==c)
              {
                cout << s << "\n";
                break;
              }
          }
          continue;
        }
      in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа
      {
        string t=T[j];
        int pos = find_subctr(t,s);
        if(pos>=0)
          {
            cout << s << "\n";
            break;
          }
      }
    }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)

typedef long long ll;

int find_subctr(string t, string s)

{

const int p = 97; // основание системы счисления для хеширования строк

// вычисляем степени числа P, чтобы ускорить процесс хеширования

vector<ll> p_pow (s.length());

p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i)

p_pow[i] = p_pow[i-1] * p;

// вычисляем хеши всех префиксов строки S

vector<ll> h (s.length());

for (size_t i=0; i<s.length(); ++i)

{

h[i] = (s[i] - 't' + 1) * p_pow[i];

if (i) h[i] += h[i-1];

}

// посчитаем хеш строки Т

ll h_t = 0;

for (size_t i=0; i<t.length(); ++i)

h_t += (t[i] - 't' + 1) * p_pow[i];

// сравниваем хеши строки T и подстрок S длины |T|

for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)

{

ll cur_h = h[i+t.length()-1];

if (i) cur_h -= h[i-1];

// если равенство выполняется хотя бы один раз, мы прекращаем поиск

if (cur_h == h_t * p_pow[i])

return int(i);

}

return -1;

}

int main()

{

vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C

int n;

cin >> n;

string tmp;

getline(cin,tmp);

in_range(i,0,n)

{

getline(cin,tmp);

if(tmp.length()==1) C.push_back(tmp);

T.push_back(tmp);

}

while(getline(cin,tmp))

{

S.push_back(tmp);

}

in_range(i,0,S.size())

{

string s=S[i];

if(s=="") continue; // отсекаем случай пустой строки

if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором

{

in_range(j,0,C.size())

{

string c=C[j];

if(s==c)

{

cout << s << "\n";

break;

}

continue;

}

in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа

{

string t=T[j];

int pos = find_subctr(t,s);

if(pos>=0)

{

cout << s << "\n";

break;

}

return 0;

}

Алгоритм

Мы последовательно перебираем все строки [latex]s[/latex] из набора [latex]S[/latex]. Для каждой из них найдем вхождение хотя бы одной строки [latex]t[/latex] из набора [latex]T[/latex]. Для этого мы воспользуемся алгоритмом Рабина-Карпа. Он заключается в следующем: мы сравниваем подстроки [latex]s[/latex] длины [latex]\left | t \right |[/latex] со строкой [latex]t[/latex], предварительно закодировав их с помощью хеша. Если после мы перебрали все подстроки, но так и не получили равенство, строка [latex]t[/latex] не является подстрокой [latex]s[/latex] и мы переходим к следующему образцу.

Однако данный алгоритм не целесообразно использовать для строк единичной длины. Про большом количестве таких строк неэффективность алгоритма становится очень заметной. Поэтому мы создаем отдельный набор образцов, состоящих ровно из одного символа. Если на вход поступает строка единичной длины, мы просто ищем ее в этом наборе за [latex]O(n)[/latex].

Код программы

Засчитанное решение на сайте e-olymp.com

Related Images:

e-olymp 1342. Периодические строки

24/04/2016 by Кондратюк Настя

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

Условие задачи

Будем говорить, что символьная строка имеет период [latex]k[/latex], если она может быть образована путем объединения одной или нескольких одинаковых строк длиной [latex]k[/latex]. Например, строка «[latex]abcabcabcabc[/latex]» имеет период [latex]3[/latex], так как она может быть образована путём объединения [latex]4[/latex]-х строк «[latex]abc[/latex]». Она также имеет период [latex]6[/latex] (объединение двух строк «[latex]abcabc[/latex]») и [latex]12[/latex] (сама строка «[latex]abcabcabcabc[/latex]»).

Напишите программу определяющую наименьший период заданной строки.

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

В первой строке задано количество тестовых случаев [latex]N[/latex] во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более [latex]80[/latex] символов без пробелов.

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

Вывести для каждого тестового случая искомое значение наименьшего периода строки. Разные тестовые случаи должны быть разделены пустой строкой.

Тесты

Входные данные	Выходные данные
2 HoHoHo mama	2 2
2 abcdefg abcabcabc	7 3
3 b bbb bbbbb	1 1 1

Код программы

    #include <iostream>
    #include <cstring>
    using namespace std;
     
    int strPeriod(char *str){
        int period;
        period = strlen(str); // 
        for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку                    
                                                 на подстроки*/
                int j;
            for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа,
                                              чтобы не выйти за границы строки*/
                if(str[j] == str[j+i]){
                    j++;
                }
                else{
                    break;
                }
            }
        if(j == (strlen(str) - i)){  /* если цикл дошел до конца 
                                        строки - период найден*/
                    period = i;
                    break;
            }
        }
     
        return period;
    }
     
    int main() {
        const int n = 81;
        int tests;
        cin >> tests;
        cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/
        char *str = new char[n];
        for(int j=0; j<tests; j++){
            cin.getline(str, n);
            cout << strPeriod(str);
            if(j != tests - 1){
                cout << endl << endl;
            }
        }
        return 0;
    }

#include <iostream>

#include <cstring>

using namespace std;

int strPeriod(char *str){

int period;

period = strlen(str); //

for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку

на подстроки*/

int j;

for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа,

чтобы не выйти за границы строки*/

if(str[j] == str[j+i]){

j++;

}

else{

break;

}

if(j == (strlen(str) - i)){ /* если цикл дошел до конца

строки - период найден*/

period = i;

break;

}

return period;

}

int main() {

const int n = 81;

int tests;

cin >> tests;

cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/

char *str = new char[n];

for(int j=0; j<tests; j++){

cin.getline(str, n);

cout << strPeriod(str);

if(j != tests - 1){

cout << endl << endl;

}

return 0;

}

ideone.com

Засчитанное решение на e-olymp.com

Решение

Строка длины [latex]s[/latex] может быть образована подстрокой, длина которой не превышает половины длины строки. Следовательно, период лежит в промежутке [latex]\left [ 1;s/2 \right ][/latex], либо равен длине строки. Последовательно разбивая строку на подстроки длиной от [latex]1[/latex] до [latex]s/2[/latex], проверяем равны ли они между собой. Если такие подстроки не нашлись, то период равен длине строки.