TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3046
  • 题目
  • P3046子串计数
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    给你一个由小写字母“a,b,c,d,e”构成的字符串S,请找出S中包含了多少个不同的长度为N的子串。例如,给出的字符串是"daababac",N的值为3,那么长度为3的不同子串有"daa"; "aab"; "aba"; "bab"; "bac",最后输出的结果是5。
    一开始给你一个空字符串S,有两个操作需要你完成:
    编号“1”:在S后添加一个字符串S’,(也就是字符串加法S=S+S’);
    编号“2”:输出当前S中包含的不相同的长度为N的字符串的个数;

    输入格式

    第一行,一个整数N
    第二行,一个整数M,表示下面有M个操作
    接下来M行,每行表示一个操作(1号操作为数字1,然后是一个空格,接着是一个字符串,2号操作只有一个数字2)。

    输出格式

    对于每个编号2的操作,输出一整数,表示所求结果。

    样例输入

    3
    4
    1 daababac
    2
    1 acc
    2

    样例输出

    5
    8

    提示

    对于 50% 的数据:1≤M≤100 1≤字符串S最终的长度≤10,000 1≤N≤8
    对于 100% 的数据:1≤M≤1000 1≤字符串S最终的长度≤200,000 1≤N≤8