题意

给定两个字符串,在第一个字符串中找到一个最大前缀作为第二个字符串的后缀。

分析

利用扩展KMP。

如果模式串的前缀\(T[0\cdots (i-1)]\)和主串\(S[(m-i)\cdots (m-1)]\)匹配,那么显然\(extand[i]=n-i\)。

枚举,找到最大的\(i\)即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注