U175023.拼接乌托邦

题目背景

至少我还在为你而歌唱，在黑暗漫长的反乌托邦。

《拼接乌托邦》是拼接了《反乌托邦 pt2》与《拼接遗憾》两首歌而成的曲子。
现在你拿到了这首歌的完整主旋律歌词串，以及若干段歌词碎片。你可以按给定顺序选择或者不选择每一块碎片，把选中的碎片首尾相接拼在一起。
求拼出来的字符串，和完整主旋律歌词串的最长公共前缀长度。

题目描述

给定一个主旋律字符串 S（完整歌词），再给出 n 块歌词碎片 (T_1,T_2,\dots,T_n)。
你必须保持碎片原本的先后顺序，每一块碎片二选一：选它或者跳过它。选中的碎片直接拼接，不能切割碎片内部字符。
设拼接得到的字符串为 P，请你求出 P 与 S 的最长公共前缀的长度。

规则：

1. 碎片顺序不可打乱；
2. 碎片不能切开，要选就整块加入；
3. 一旦在某块碎片里字符匹配失败，这块碎片剩下的字符全部作废，不能继续匹配；
4. 如果已经匹配完整个主旋律 S，后续碎片无需处理。

至少我还在为你而歌唱
3
至少我
还在为你
黑暗漫长

8

数据范围

(1\le |S| \le 10^5)
(1\le n \le 10^5)
(\sum |T_i| \le 10^5)
字符串仅包含中文汉字（每个汉字当作单个字符处理）
时限：1s
内存：256MB

提示

维护一个指针 pos，记录当前已经匹配到主旋律的第 pos 位。依次遍历碎片，逐个字符比对，匹配成功指针后移；一旦失配，直接结束当前碎片的比对。