Concatenation with intersection（2800/z算法/树状数组/双指针）

题目：http://codeforces.com/contest/1313/problem/E 参考：http://codeforces.com/blog/entry/74146 题意：给定字符串a,b,s。求子串组合数使得 a [ l 1 , r 1 ] + b [ l 2 , r 2 ] = = s a[l1,r1]+b[l2,r2]==s a[l1,r1]+b[l2,r2]==s，要求 [ l 1 , r 1 ] , [ l 2 , r 2 ] [l1,r1],[l2,r2] [l1,r1],[l2,r2]交集非空。 题解：用z算法求出a在s中的最长前缀 l c p lcp lcp，b在s中的最长后缀 l c s lcs lcs。从左到右枚举a字符串，取定 l 1 l_1 l1​，那么相应的 r 2 r_2 r2​取值为 l 1 < = r 2 < = l 1 + m − 2 l_1