题目名称 90. 翻译玛雅著作
输入输出 writing.in/out
难度等级 ★★★
时间限制 3000 ms (3 s)
内存限制 128 MiB
测试数据 16
题目来源 Gravatarcqw 于2008-09-08加入
开放分组 全部用户
提交状态
分类标签
离散化
分享题解
通过:43, 提交:126, 通过率:34.13%
Gravatarf0rest 100 0.080 s 3.15 MiB C++
GravatarZXCVBNM_1 100 0.084 s 3.18 MiB C++
GravatarceerRep 100 0.086 s 3.18 MiB C++
Gravatarsqyon 100 0.092 s 3.18 MiB C++
Gravatarsqyon 100 0.094 s 3.18 MiB C++
Gravatarxy 100 0.113 s 2.96 MiB C++
Gravatar阿狸 100 0.174 s 2.98 MiB C++
Gravatar郭乾乐 100 0.188 s 16.53 MiB C++
Gravatar甘罗 100 0.287 s 0.17 MiB Pascal
GravatarFoolMike 100 0.293 s 0.17 MiB Pascal
本题关联比赛
模拟测试2
20100927
NOIP_2
NOIP_2
20200622
关于 翻译玛雅著作 的近10条评论(全部评论)
字符串处理,小可认为最简单的方法就是比较各式各个字母出现的次数
GravatarFoolMike
2014-10-31 21:12 4楼
mark
GravatarHouJikan
2014-09-08 23:02 3楼
开几个数组记录,O(n)扫描一下,注意对正在处理的区间的操作
Gravatarsqyon
2014-08-17 19:34 2楼
线性匹配使用O(n)的算法
Gravatar任杰
2014-08-17 12:05 1楼

90. 翻译玛雅著作

★★★   输入文件:writing.in   输出文件:writing.out   简单对比
时间限制:3 s   内存限制:128 MiB

【问题描述】

初期研究证实解读玛雅文是一项比预期复杂的任务,即使在过了两百年以后,也只有很少的内容能被人们真正理解,其实也仅是在最近的三十年人们才真正地对它展开研究。

玛雅文是基于石刻的一些被认为是象形符号的表征声音的小图画,通常把一些象形符号放在不同的位置就组合成了一个玛雅文中的词。

解读玛雅文时遇到的问题之一是在读的顺序上,在摆放几个符号以拼写成一个词的时候,玛雅文创作者有时按他们的主观感觉来决定符号的摆放位置,而不是按照任何特殊规则。这导致的问题是,尽管知道了许多符号的发音,但是考古学家们有时仍旧不能确定一个词的读法。

考古学家正在寻找一个特殊的词w,他们知道组成它的各个符号,但是他们不知道所有这些符号的可能排列方法。后来他们听说你来了,就想求得你的帮助。他们将给你提供g个组成词w的符号,同时还有一个符号串s,里面包含了他们在研究石刻时发现的所有符号。请帮助他们计算一下词w有多少种可能的拼写方案。

写一个程序,给定组成w的符号和石刻中的符号串s,计算s中w的可能拼写方案出现的次数;确切点说,s中每一个连续的长度为g的符号串都可能是w中那些符号的一个排列。

【输入格式】

第一行包含两个整数:g和|s|,空格隔开;

第二行包含g个连续的字符,分别表示组成w的g个符号,字符有效范围为'a'-'z'和'A'-'Z',大小写字母有区别;

第三行包含|s|个连续的字符,表示石刻中的符号,字符有效范围为'a'-'z'和'A'-'Z',大小写字母有区别。

【输出格式】

只有一行,即s中w的可能拼写方案出现的次数。

【输入样例】

4 11
cAda
AbrAcadAbRa

【输出样例】

2

【数据范围和约定】

1 ≤ g ≤ 3 000 w中的符号个数;

g ≤ |s| ≤ 3 000 000 |s|是s中符号的个数。

其中有50分的测试数据g≤ 1000。

对使用Pascal语言的选手的重要提醒:

FreePascal中默认字符串类型变量长度不能超过255个字符.