小编pgi*_*itu的帖子

Charles对我来说显示IP地址而不是域名.有没有其他人看到过这个问题.请参阅附带的屏幕截图

输入:

有一个长字符串S,我们有一个整数数组A,表示字符串的前缀,S如A[i]表示前缀S[0..A[i]]

输出:

返回一个数组Output[]大小相同的作为A其中Output[i]是的最长匹配后缀的长度S[0..A[i]]和S

样本输入:

S = "ababa"
A[]=[0, 1, 2, 3, 4]

样本输出:

Output[]=[1,0,3,0,5]

最天真的算法,我是每一个A[i]刚刚匹配之间的字符数S[0..A[i]],并S从两个字符串的结尾.但是这个算法的位置是O(n^2)n是原始String S的长度.

问题:
是否有更好的算法预处理字符串S,然后可以快速返回整个输入数组的最长长度后缀？

这是我遇到的问题

确定性有限自动机（DFA）是一种有限状态机，它接受/拒绝符号的有限字符串，并且仅对每个输入字符串产生唯一的自动化计算（或运行）。

DFA可以使用状态图表示。例如，在下面显示的自动机中，存在三种状态：S0，S1和S2（以圆圈图形表示）。自动机将0和1的有限序列作为输入。对于每个状态，都有一个过渡箭头，分别指向0和1的下一个状态。读取符号后，DFA会跟随过渡箭头从一个状态确定地跳到另一状态。例如，如果自动机当前处于状态S0，并且当前输入符号为1，则它确定性地跳到状态S1。DFA具有计算开始的起始状态（以图形表示从无处进入的箭头）和一组接受状态（以双圆圈图形表示），它们有助于定义计算何时成功。

这些是DFA接受的一些字符串，

0
00
000
11
110
1001

您会在输入中获得一个DFA，并输入一个整数N。您必须知道给定DFA接受多少个长度为N的不同字符串。

笔记

• 假设每个状态都有两个输出边（一个为0，一个为1）。两个输出边缘都不会进入同一状态。
• 可能有多个接受状态，但只有一个开始状态。
• 起始状态也可以是接受状态。

输入格式

• 状态从0到K-1编号，其中K是DFA中的状态总数。
• 您将获得三个数组A，B，C和两个整数D和N。
• 数组A表示从状态i到状态A [i]的0个边沿，对于所有0？一世 ？K-1
• 数组B表示从状态i到状态B [i]的1条边，对于所有0？一世 ？K-1
• 数组C包含所有接受状态的索引。
• 整数D表示开始状态。
• 整数N表示您必须计算给定DFA接受多少个长度为N的不同字符串。

约束条件

1 ? K ? 50 
1 ? N ? 10^4

范例：

对于图像中显示的DFA，输入为

A = [0, 2, 1]
B = [1, 0, 2]
C = [0]
D = 0

输入1

N = 2
Strings '00' and '11' are only strings on length 2 which are accepted. So, answer is 2.

输入2

N = …