绿色的节点表示是【2】中代码第28行新建的节点z——即S[1,...,i+1]所属的节点(【2】中的附录图1中的z), 换言之是每次新读入字符产生的新的前缀属于的节点....而浅粉色的节点是【2】中代码48行从x拆分出来的y(【2】中的附录图3中的y), 换言之, 是拆分出来的节点. 也就是S的sam节点的个数>=S的长度. 多出来的都是拆分出来的节点....结论: 对于浅粉色的节点, A是成立的, 对于绿色的节点, A是不成立的, 而要将A的叙述改成
父节点的endpos大小恰好等于所有子节点们的endpos大小之和再加1, 而且加的这个1就是父节点中的最长的那个...for (int i = 1;i<=len; i++)
{
printf("%lld\n", ans[i]);
}
return 0;
}
ac情况
Accepted
参考
【1】《史上全网最清晰后缀自动机学习...(一)基本概念入门》
【2】《史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法》