#P5646. [模版题]最长共同前缀长度

    ID: 4647 传统题 1000ms 256MiB 尝试: 4 已通过: 3 难度: 4 上传者: 标签>CF1600普及+/提高-Z 算法扩展 KMP最长公共前缀

[模版题]最长共同前缀长度

Description

给出模板串A和子串B,长度分别为lenA和lenB

要求在线性时间内,对于每个A[i](1<=i<=lenA),求出A[i..lenA]与B的最长公共前缀长度

Format

Input

输入A,B两个串,(lenB<=lenA<=1000000)

Output

输出lenA个数,表示A[i...lenA]与B的最长公共前缀长度,每个数之前有空格

Samples

aabbabaaab
aabb
4 1 0 0 1 0 2 3 1 0