CF竞赛题目讲解_CF1721E(fail指针 + KMP的next数组)
2022-10-24 16:33 作者:Clayton_Zhou | 我要投稿
AC 代码
https://codeforces.com/contest/1721/submission/177717775
题意：
已知字符串s，t，连接s和t；计算所得字符串s+t的前缀函数；
即位置|s|+1、|s|+2、…、|s|+|t|上的前缀函数的值（|s|和|t|分别表示字符串s和t的长度）；
字符串a的前缀函数是序列p1，p2，…，p|a|，其中pi是k的最大值，使得k＜i，a[1..k]＝a[i−k+1..i]
题解：
fail指针 + KMP的next数组
使用AC自动机的fail指针和KMP的next数组概念提高查询(模式匹配)速度
