2013集训队论文答辩(罗干)演示文稿.ppt

twostrings 杭州学军中学罗干 给定两个字符串A和B 有五种操作操作1在A串开头添加一个字符操作2在A串结尾添加一个字符操作3在B串开头添加一个字符操作4在B串结尾添加一个字符操作5询问当前的B串在当前A串中出现的次数 保证字符均为小写字母 且A B串初始非空 问题描述 第一行第二行分别为初始的A串和B串 第三行一个整数m 表示操作的次数 接下来m行 每行表示一个操作 每行第一个数为一个在1 5之间的数字 若其值不为5 则在数字后会有一个小写字母 对于每个询问 每行输出一个整数 表示B串在A串中出现的次数 输入与输出格式 样例输入 ababca754b53a1a55 样例输出 2211 样例解释 样例输入 ababca754b53a1a55 10 的数据中 最终A串和B串长度之和小于等于200 操作数小于等于10 30 的数据中 最终A串和B串长度之和小于等于2000 操作数小于等于1000 另有20 的数据 操作3和4的次数之和小于等于100 100 的数据中 最终A串和B串长度之和小于等于200000 操作数小于等于200000 数据规模 模拟每个操作 对于每次询问 直接枚举B串在A串中的位置 然后直接比较预计得分 算法1模拟法 10分 在算法1的基础上 对于询问我们用KMP算法去匹配预计得分 算法2KMP优化模拟法 30分 离线优化算法2求出最终的 大A串 每次询问相当于询问大A串某一段内有几个B串 算法3离线优化模拟法 大A串ABABABC 红色表示此时的A串 B串AB完整在BABA中出现的有1个B串 有三四操作重新做KMP 记下从哪几个位置开始与B串匹配询问变成 L R Len B 1 内位置的个数L递减 R递增 询问时间为O 1 算法3离线优化模拟法 大A串ABABABCB串AB那么匹配的位置有ABABABCABABABCABABABC只有第二个在范围内 答案是1 定义len B 当前B串的长度 操作1O 1 操作2O 1 操作3O n 操作4O n 操作5O n O 1 预计得分 算法3离线优化模拟法 50分 本题数据范围十万级别 字符串处理 后缀数组 后缀数组离线处理算法 算法4 离线将A B串最终的结果串并在一起后缀数组 第一步在线 离线 大A串 ABABC大B串 ABA最终串 ABABC ABA后缀数组排序后 AABAABABC ABAABC ABABABABC ABABC ABAC ABA ABA 当前B串在A串第i到第i Len B 1处出现等同于当前B串对应后缀与A串第i个后缀的Lcp Len B 第二步求出可行的后缀区间 大A串 ABABC大B串 ABA下划线表示当前的 第二步求出可行的后缀区间 后缀数组排序后 AABAABABC ABAABC ABABABABC ABABC ABAC ABA ABA 第二步求出可行的后缀区间 当前B串 找出所有与当前B串对应后缀Lcp Len B 的后缀在后缀数组中连续 可行区间 倍增预处理height数组 如何求解 统计可行区间中合法位置个数 第三步统计合法的A串起始位置 后缀数组排序后 AABAABABC ABAABC ABABABABC ABABC ABAC ABA ABA 可行区间 合法起始位置 第二步求出可行的后缀区间 当前B串 这就是所求答案 我们定义合法的位置为 对于大A串的位置i i i Len B 1 这一段都在当前的A串中 任意一个操作只改变至多一个位置的合法性树状数组维护后缀数组某一段内合法位置个数 第四步树状数组维护 操作1O logN 操作2O logN 操作3O logN 操作4O logN 操作5O logN 预计得分 至此彻底解决了此题 100分 得分情况估计 回顾 原问题 考虑本质 离线算法 后缀数组 后缀操作 离线优化 朴素算法 在线 离