思路：这题确实大帝做得很机智！字符串先求最长前缀，反的字符串再求一次最长前缀，然后就可以搞了。
每个子串出现的次数就是最长前缀的次数嘛！
#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 100005 typedef long long ll; typedef unsigned long long ull; using namespace std; void EKMP(char *s,char *t,ll *next,ll *extend)//s[]为主串，t[]为模版串 { int i,j,p,l; int len=strlen(t); int len1=strlen(s); memset(next,0,sizeof(next)); memset(extend,0,sizeof(extend)); next[0]=len; j=0; while(1+j =1;i--) sum[i]+=sum[i+1]; reverse(S,S+len1); reverse(T,T+len2); EKMP(S,T,next,extend); for(int i=0;i =1;i--) sum1[i]+=sum1[i+1]; ll ans=0; for(int i=1;i