科大讯飞笔试 8.13 AK

睡到14：37才醒，迟到了37min，还好题目不难。

编程题用时17min，
总用时40min。

题3：数量级10的5次方，枚举所有的子串复杂度n方，肯定不行。

A中子串数量为 n * (n + 1) / 2

B中新子串的数量计算如下：
用hash表h记录a数组各元素的坐标。
依次遍历b数组的每个元素，再根据h获取对应a中的坐标
然后两个坐标同时向后移动，直到不匹配的时候两者就出现了不同子串，统计b坐标剩余的长度，即为当前节点的新子串数量。
比如：
a: ...ABC..
b: ...ABDSD

从A开始匹配，b的D与a的C无法匹配，则ABD、ABDS、ABDSD都是在a中不曾出现的子串，数量为 （字符串长度-D的坐标+1）
优化一下：两个坐标移动过程中相同的公共节点数量也是b坐标剩余的长度，所以可以直接计算。
即由于A匹配过最长的子串了，B的数量也是（字符串长度-D的坐标+1），

则下一步可以直接开始从D开始匹配。

时间复杂度O(N)
不太擅长讲解，可能不太清楚

代码没保存，因为直接在线提交的，没用上本地ide

#科大讯飞信息集散地#