题目链接：https://cn.vjudge.net/contest/318888#problem/J

 

思路：

 

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #include <math.h>
  7 #include <queue>
  8 #include <set>
  9 
 10 #define INF 0x3f3f3f3f
 11 #define pii pair<int,int>
 12 #define LL long long
 13 using namespace std;
 14 typedef unsigned long long ull;
 15 const int MAXN = 2e5 + 10;
 16 int t;
 17 int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
 18 int sta[MAXN];
 19 int cnt[MAXN];
 20 void Suffix(int *r, int *sa, int n, int m)
 21 {
 22     int i, j, k, *x = wa, *y = wb, *t;
 23     for(i = 0; i < m; ++i) ws_[i] = 0;
 24     for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
 25     for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
 26     for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
 27     for(j = 1, k = 1; k < n; j *= 2, m = k)
 28     {
 29         for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
 30         for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
 31         for(i = 0; i < n; ++i) wv[i] = x[y[i]];
 32         for(i = 0; i < m; ++i) ws_[i] = 0;
 33         for(i = 0; i < n; ++i) ws_[wv[i]]++;
 34         for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
 35         for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
 36         t = x;
 37         x = y;
 38         y = t;
 39         for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
 40             x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
 41     }
 42 }
 43 int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
 44 char s[MAXN],ss[MAXN];
 45 int indexx[MAXN],vis[200];
 46 void calheight(int *r,int *sa,int n)
 47 {
 48     int i,j,k=0;
 49     for(i=1; i<=n; i++)Rank[sa[i]]=i;
 50     for(i=0; i<n; height[Rank[i++]]=k)
 51         for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
 52 }
 53 
 54 
 55 int main(){
 56     while (~scanf("%d",&t) && t){
 57         memset(r,0, sizeof(r));
 58         memset(sa,0, sizeof(sa));
 59         memset(Rank,0, sizeof(Rank));
 60         scanf("%s%s",s,ss);
 61         int len1 = strlen(s);
 62         int len2 = strlen(ss);
 63         s[len1] = '@';
 64         for (int i=0;i<len2;i++){
 65             s[len1+1+i] = ss[i];
 66         }
 67         s[len1+len2+1] = '\0';
 68         for (int i=0;i<len1+len2+1;i++){
 69             r[i] = s[i];
 70         }
 71         r[len1+len2+2] = 0;
 72         Suffix(r,sa,len1+len2+2,300);
 73         calheight(r,sa,len1+len2+1);
 74         LL sum = 0,ans = 0; //sum代表栈里面对答案的贡献值，cnt数组记录的是一个组内的后缀数
 75         int top = 0;
 76         for (int i=1;i<len1+len2+2;i++){  // 处理A和它前面B的公共前缀
 77             if (height[i]<t){
 78                 top = 0;
 79                 sum = 0;
 80                 continue;
 81             }
 82             int num = 0;
 83             while (top && height[i]<sta[top]){
 84                 sum -= (LL)(sta[top]-t+1)*cnt[top]; //在这儿比height[i]大的都要变成height[i]，所以先减去先前加上去的
 85                 sum += (LL)(height[i]-t+1)*cnt[top]; //乘cnt[top]的原因是可能有多个合并成一个了，比如4,5,3，那么4和5都只能以3来计算
 86                 num += cnt[top]; //那么此时这三个可以合并在一起，cnt个数就是3，和就是3*3=9
 87                 top--;
 88             }
 89             sta[++top] = height[i];
 90             if (sa[i-1]>len1){
 91                 sum += (LL)(height[i]-t+1);
 92                 cnt[top]  = num+1;
 93             }
 94             else
 95                 cnt[top] = num;
 96             if (sa[i]<len1)
 97                 ans += sum;
 98         }
 99         sum = 0,top = 0; 
100 
101         for (int i=1;i<=len1+len2+2;i++){ //处理B和它前面的A的公共前缀
102             if (height[i]<t){
103                 top = 0;
104                 sum = 0;
105                 continue;
106             }
107             int num = 0;
108             while (top && height[i]<sta[top]){
109                 sum -= (LL)(sta[top]-t+1)*cnt[top]; 
110                 sum += (LL)(height[i]-t+1)*cnt[top]; 
111                 num += cnt[top];  
112                 top--;
113             }
114             sta[++top] = height[i];
115             if (sa[i-1]<len1){
116                 sum += (LL)(height[i]-t+1);
117                 cnt[top]  = num+1;
118             }
119             else
120                 cnt[top] = num;
121             if (sa[i]>len1)
122                 ans += sum;
123         }
124         printf("%lld\n",ans);
125     }
126     return 0;
127 }