扩展KMP
题目意思：
题目的 hit 解释很清楚。
本题要点：
1、 做法： 先把 s1 和 s2 来个翻转。以 s1 为母串， s2 为子串， 运行 扩展 KMP 算法，
extend[i] 表示 s2的子串 s2[i, … , extend[i] + i - 1] 与 s1 的子串 s1[0, …, extend[i] - 1] 相等。
这样就说明了， 以下的子串都相等。
s2[i, ... , extend[i] + i - 2] == s1[0, ..., extend[i] - 2]
s2[i, ... , extend[i] + i - 3] == s1[0, ..., extend[i] - 3]
s2[i, ... , extend[i] + i - 4] == s1[0, ..., extend[i] - 4]
...
s2[i, ... , i + 2] == s1[0, ..., 2]
s2[i, ... , i + 1] == s1[0, ..., 1]
所以，当遇到 extend[i] != 0 时候，从 1 累加到 extend[i], 等差数列，和为 extend[i] * (extend[i] + 1) / 2
2、以上各式子，累加起来就是题目所求。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 1e6 + 10;
const long long mod = 1e9 + 7;
int Next[MaxN];
int extend[MaxN]; // extend[i] 表示 子串 T与 母串 S[i, n-1]的最长公共前缀
char s1[MaxN], s2[MaxN];
int T;//预处理next 数组
void getNext(char* str)
{
int i = 0, j, po, len = strlen(str);Next[0] = len; while(i + 1 < len && str[i] == str[i + 1]) // 计算 next[1]++i;Next[1] = i;po = 1; //初始化 po位置for(int i = 2; i < len; ++i){
if(Next[i - po] + i < Next[po] + po) //第一种情况{
Next[i] = Next[i - po];}else{
//第二种情况，要继续匹配才能得到next[i]的值j = Next[po] + po - i; if(j < 0)j = 0; //如果i>po+next[po],则要从头开始匹配while(i + j < len && str[j] == str[j + i])++j;Next[i] = j;po = i;}}
}//计算extend 数组
void exkmp(char* s1, char* s2) // s2 是子串，s1是母串
{
int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);getNext(s2);while(i < l2 && i < len && s1[i] == s2[i])++i;extend[0] = i;po = 0; //初始化po的位置for(i = 1; i < len; ++i){
if(Next[i - po] + i < extend[po] + po){
extend[i] = Next[i - po];}else{
j = extend[po] + po - i;if(j < 0)j = 0;while(i + j < len && j < l2 && s1[j + i] == s2[j]){
++j;}extend[i] = j;po = i;}}
}void reverse(char *str)
{
int len = strlen(str);for(int i = 0; i < len / 2; ++i){
swap(str[i], str[len - i - 1]);}
}int main()
{
scanf("%d", &T);while(T--){
scanf("%s%s", s1, s2);reverse(s1);reverse(s2);exkmp(s1, s2);long long ans = 0;int len = strlen(s1);for(int i = 0; i < len; ++i){
if(extend[i] != 0){
long long tmp = (long long)extend[i] * (extend[i] + 1) / 2;ans = (ans + tmp) % mod; }}printf("%lld\n", ans);}return 0;
}/* 2 aaaaa aa abababab aba *//* 13 19 */