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

Question

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

Миха Лыч Ученик (152), закрыт 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

Дополнен 3 года назад

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

#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;
}

Answer 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");
}

Answer 2

Примерно:
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.