Mail.ruПочтаМой МирОдноклассникиИгрыЗнакомстваНовостиПоискСмотриComboВсе проекты

ЗАДАЧА можно на С++ и Pascal Расшифровка письменности Майя Темы: Строки, Сортировка подсчетом

Миха Лыч Ученик (129), закрыт 3 недели назад
Дана строка и подстрока. Требуется определить, сколько раз в строке встречалась подпоследовательность, состоящая из символов подстроки.
Расшифровка письменности Майя оказалась более сложной задачей, чем предполагалось ранними исследованиями. На протяжении более чем двух сотен лет удалось узнать не так уж много. Основные результаты были получены за последние 30 лет.

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

Одна из проблем расшифровки письменности Майя заключается в определении этого порядка. Рисуя значки некоторого слова, писатели Майя иногда выбирали позиции для значков, исходя скорее из эстетических взглядов, а не определенных правил. Это привело к тому, что, хотя звуки для многих значков известны, археологи не всегда уверены, как должно произноситься записанное слово.

Археологи ищут некоторое слово W. Они знают значки для него, но не знают все возможные способы их расположения. Поскольку они знают, что Вы приедете на IOI ’06, они просят Вас о помощи. Они дадут Вам g значков, составляющих слово W, и последовательность S всех значков в надписи, которую они изучают, в порядке их появления. Помогите им, подсчитав количество возможных появлений слова W.

Задание
Напишите программу, которая по значкам слова W и по последовательности S значков надписи подсчитывает количество всех возможных вхождений слова W в S, то есть количество всех различных позиций идущих подряд g значков в последовательности S, которые являются какой-либо перестановкой значков слова W .

Ограничения
1 ≤ g ≤ 3 000, g – количество значков в слове W

g ≤ |S| ≤ 3 000 000 где |S| – количество значков в последовательности S

Входные данные
На вход программы поступают данные в следующем формате:

СТРОКА 1: Содержит два числа, разделенных пробелом – g и |S|.
СТРОКА 2: Содержит g последовательных символов, с помощью которых записывается слово W . Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.
СТРОКА 3: Содержит |S| последовательных символов, которые представляют значки в надписи. Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.

Выходные данные
Единственная строка выходных данных программы должна содержать количество возможных вхождений слова W в S.

Оценивание
Для части тестов, оцениваемых в 50 баллов, выполняется ограничение g ≤ 10.

Примеры
входные данные
4 11
cAda
AbrAcadAbRa

выходные данные
2
Дополнен 1 месяц назад
ПЫТАЛСЯ РЕШИТЬ, НО ПРОХОДИТ ТОЛЬКО ОДИН ТЕСТ, не очень понимаю что от меня хотят помогите разобраться, если надо заплачу

#include
using namespace std;
int main()
{
//freopen("writing.in", "r", stdin);
//freopen("writing.out", "w", stdout);
int a,b,d,c;
cin>>d>>c;
string str,str1;
cin>>str>>str1;
cout <<c/d;
return 0;
}
Лучший ответ
Николай Веселуха Высший разум (229248) 1 месяц назад
#include <iostream>
#include <string>
#include <set>
using namespace std;
bool copmare(string& sa, string& sb) {
set<char> a;
for (auto x : sa) a.insert(x);
set<char> b;
for (auto x : sb) b.insert(x);
return a == b;
}
size_t counter(std::string& seq, string& word) {
auto count = 0U;
auto n = word.length();
const auto m = seq.length();
for (auto i = 0; n < m; ++i, ++n) {
string sa(seq.begin() + i, seq.begin() + n);
if (copmare(sa, word)) ++count;
}
return count;
}
int main() {
size_t g, l;
cin >> g >> l;
string x;
cin >> x;
string w(x.begin(), x.begin() + g);
cin >> x;
string s(x.begin(), x.begin() + l);
auto count = counter(s, w);
cout << count << '\n';
system("pause > nul");
}
Остальные ответы
Ардов Александр Мастер (1361) 1 месяц назад
Примерно:
Program Bd_Maya
var
a,b:integer
begin
a=b
Write(a,"Майя1",string)=count(a)
Write(b,"Майя2",string)=count(b)
if
count(a)>count(b)=value(1)
count(a)<count(b)=value(2)
count(a)=count(b)=value(3)
then
Write(value)
end.
Миха ЛычУченик (129) 1 месяц назад
спасибо сейчас проверю
Миха ЛычУченик (129) 1 месяц назад
ошибка
Похожие вопросы
Также спрашивают