题目链接

题目描述

给定n个字符,m个查询,每个查询包括两个数字,要求从下标为这两个字符串中找到一个最长公共子串,并且这个子串为这n个字符的前缀。

解题思路

AC自动机模板稍作修改。写这种题目各种绝望,链表写着写着发现不行,然后就创建静态链表,接着又是一阵GG,最后还是数组写的比较好,该题解写完命已呜呼。
步入正题,我们先根据给定的n个字符创建线段树,节点之中保存这该前缀的长度。然后就是常规的建立fail指针。
然后我们将要查询的第一个字符先跑一遍AC自动机,并在中留下标记,表明这是第一个字符串的子串并且为这n个字符的前缀,紧接着跑第二个字符串,如果遍历到某个节点,这个节点已经被第一个标记过了,那么就表明该节点就是这两个串的公共子串并且是这n个字符的某个前缀,现在的目标就是应该不断刷新找出最大值。

代码部分