Common Substrings

A substring of a string T is defined as:

Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):

You are to give the value of |S| for specific A, B and K.

The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.

1 ≤ |A|, |B| ≤ 10⁵
1 ≤ K ≤ min{|A|, |B|}
Characters of A and B are all Latin letters.

  1 #include<cstdlib>  2 #include<cstdio>  3 #include<algorithm>  4 #include<cstring>  5 #ifdef WIN32  6 #define fmt64 "%I64d"  7 #else  8 #define fmt64 "%lld"  9 #endif 10 using namespace std; 11 const int maxn = (int)2.5e5,sigma = 26; 12 char str[maxn]; 13 int k; 14 int cmp(int, int); 15 struct Sam{ 16     int ch[maxn][sigma << 1],par[maxn],stp[maxn],right[maxn],times[maxn],id[maxn]; 17     int sz,last; 18     int idx(char x){ 19         if(‘a‘ <= x && x <= ‘z‘) return x - ‘a‘; 20         else return x - ‘A‘ + 26;                               21     } 22     void init(){ 23         for(int i = 1; i <= sz; ++i){ 24             memset(ch[i],0,sizeof(ch[i])); 25             right[i] = times[i] = par[i] = stp[i] = 0; 26         } 27         sz = last = 1; 28     } 29     void add(int c){ 30         stp[++sz] = stp[last] + 1; 31         int p = last, np = sz; 32         for(; !ch[p][c]; p = par[p]) ch[p][c] = np; 33         if(!p) par[np] = 1; 34         else{ 35             int q = ch[p][c]; 36             if(stp[q] != stp[p] + 1){ 37                 stp[++sz] = stp[p] + 1; 38                 int nq = sz; 39                 memcpy(ch[nq],ch[q],sizeof(ch[q])); 40                 par[nq] = par[q]; 41                 par[q] = par[np] = nq; 42                 for(; ch[p][c] == q; p = par[p]) ch[p][c] = nq; 43             } 44             else par[np] = q; 45         } 46         last = np; 47     } 48     void ins(char *pt){ 49         int i; 50         init(); 51         for(i = 0; pt[i]; ++i) add(idx(pt[i])); 52     } 53     void prep(char *pt){ 54         int i,x = 1; 55         for(i = 1; i <= sz; ++i) id[i] = i; 56         sort(id + 1, id + sz + 1, cmp); 57         for(i = 0; pt[i]; ++i){ 58             x = ch[x][idx(pt[i])]; 59             ++right[x]; 60         } 61         for(i = 1; i <= sz; ++i) 62             if(par[id[i]]) right[par[id[i]]] += right[id[i]]; 63     } 64     void comp(char *pt){ 65         int i,x = 1,match = 0; 66         long long ans = 0; 67         for(i = 0; pt[i]; ++i){ 68             if(ch[x][idx(pt[i])]){ 69                 x = ch[x][idx(pt[i])]; 70                 match++; 71             } 72             else{ 73                 while(x && !ch[x][idx(pt[i])]) x = par[x]; 74                 if(!x) x = 1, match = 0; 75                 else match = stp[x] + 1, x = ch[x][idx(pt[i])]; 76             } 77             if(match >= k){ 78                 ans += (long long)(match - max(k, stp[par[x]] + 1) + 1) * right[x]; 79                 if(par[x] && k <= stp[par[x]]) times[par[x]]++; 80             } 81         } 82         for(i = 1; i <= sz; ++i){ 83             int t = id[i]; 84             ans += (long long)times[t] * right[t] * (stp[t] - max(k, stp[par[t]] + 1) + 1); 85             if(par[t] && k <= stp[par[t]]) times[par[t]] += times[t]; 86         } 87         printf(fmt64"\n",ans); 88     } 89 }sam; 90 int cmp(int x,int y){ 91     return sam.stp[x] > sam.stp[y]; 92 } 93 int main() 94 { 95     freopen("csb.in","r",stdin); 96     freopen("csb.out","w",stdout); 97     while(scanf("%d\n",&k) != EOF,k){ 98         scanf("%s\n",str); 99         sam.ins(str);100         sam.prep(str);101         scanf("%s\n",str);102         sam.comp(str);103     }104     return 0;105 }