CF競(jìng)賽題目講解_CF1721E(fail指針 + KMP的next數(shù)組)
2022-10-24 16:33 作者:Clayton_Zhou | 我要投稿
AC 代碼
https://codeforces.com/contest/1721/submission/177717775
題意：
已知字符串s，t，連接s和t；計(jì)算所得字符串s+t的前綴函數(shù)；
即位置|s|+1、|s|+2、…、|s|+|t|上的前綴函數(shù)的值（|s|和|t|分別表示字符串s和t的長(zhǎng)度）；
字符串a(chǎn)的前綴函數(shù)是序列p1，p2，…，p|a|，其中pi是k的最大值，使得k＜i，a[1..k]＝a[i?k+1..i]
題解：
fail指針 + KMP的next數(shù)組
使用AC自動(dòng)機(jī)的fail指針和KMP的next數(shù)組概念提高查詢(模式匹配)速度
標(biāo)簽：
