POJ 3415 Common Substrings（后缀数组）

Description

A substring of a string T is defined as:

T(i, k)=T_iT_i₊₁...T_i+k_-1, 1≤i≤i+k-1≤|T|.

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

S = {(i, j, k) | k≥K, A(i, k)=B(j, k)}.

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

Input

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.

Output

For each case, output an integer |S|.

题目大意：给两个字符串，问有多少个长度大于等于K的公共子串。

思路：首先，把两个字符串用一个未出现过的字符（如'$'）连起来，求后缀数组和height[]数组。

用每个后缀的所有前缀代表一个字符串的所有子串。

然后，按height[]的顺序从前往后扫描。

遇到第一个字符串的，就压入栈中。遇到第二个字符串的，就计算栈中与第二个字符串的长度大于等于K的公共前缀。

对于栈中每一个height[]，它与当前第二个字符串的长度大于等于K的公共前缀一共有height[]-k+1个。

sum{height[]-k+1}可以在压栈的同时统计。

用一个单调栈维护，让每个height[]只入栈和出栈一次。

最后rank小的第一个字符串和rank大的第二个字符串的长度大于等于K的公共前缀就统计出来了，统计复杂度为O(n)。

此时两个字符串反过来再做一遍即可。

代码（1469MS）：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <stack>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 char s[MAXN];

 int sa[MAXN], rank[MAXN], height[MAXN], c[MAXN], tmp[MAXN];

 int n, apart, k;

 void makesa(int m) {

     memset(c, , m * sizeof(int));

     for(int i = ; i < n; ++i) ++c[rank[i] = s[i]];

     for(int i = ; i < m; ++i) c[i] += c[i - ];

     for(int i = ; i < n; ++i) sa[--c[rank[i]]] = i;

     for(int k = ; k < n; k <<= ) {

         for(int i = ; i < n; ++i) {

             int j = sa[i] - k;

             if(j < ) j += n;

             tmp[c[rank[j]]++] = j;

         }

         int j = c[] = sa[tmp[]] = ;

         for(int i = ; i < n; ++i) {

             if(rank[tmp[i]] != rank[tmp[i - ]] || rank[tmp[i] + k] != rank[tmp[i - ] + k])

                 c[++j] = i;

             sa[tmp[i]] = j;

         }

         memcpy(rank, sa, n * sizeof(int));

         memcpy(sa, tmp, n * sizeof(int));

     }

 }

 void calheight() {

     for(int i = , k = ; i < n; height[rank[i++]] = k) {

         k -= (k > );

         int j = sa[rank[i] - ];

         while(s[i + k] == s[j + k]) ++k;

     }

 }

 struct Node {

     int height, cnt;

     Node(int height = , int cnt = ): height(height), cnt(cnt) {}

 };

 LL solve() {

     LL ans = , sum = ;

     stack<Node> stk;

     for(int i = ; i < n; ++i) {

         int cnt = ;

         while(!stk.empty() && stk.top().height >= height[i]) {

             Node t = stk.top(); stk.pop();

             cnt += t.cnt;

             sum -= t.cnt * (t.height - k + 1LL);

         }

         if(height[i] >= k) {

             cnt += (sa[i - ] < apart);

             if(cnt) stk.push(Node(height[i], cnt));

             sum += cnt * (height[i] - k + 1LL);

         }

         if(sa[i] > apart) ans += sum;

     }

     while(!stk.empty()) stk.pop();

     sum = ;

     for(int i = ; i < n; ++i) {

         int cnt = ;

         while(!stk.empty() && stk.top().height >= height[i]) {

             Node t = stk.top(); stk.pop();

             cnt += t.cnt;

             sum -= t.cnt * (t.height - k + 1LL);

         }

         if(height[i] >= k) {

             cnt += (sa[i - ] > apart);

             stk.push(Node(height[i], cnt));

             sum += cnt * (height[i] - k + 1LL);

         }

         if(sa[i] < apart) ans += sum;

     }

     return ans;

 }

 int main() {

     while(scanf("%d", &k) != EOF && k) {

         scanf("%s", s);

         apart = strlen(s);

         s[apart] = '$';

         scanf("%s", s + apart + );

         n = strlen(s) + ;

         makesa();

         calheight();

         cout<<solve()<<endl;

     }

 }

巴特西

POJ 3415 Common Substrings（后缀数组）

最新文章

热门文章