(Relax 后缀数组1.3)POJ 3415 Common Substrings(求串A和串B中长度不小于k的公共子串数)

 
#include   
#include   
#include   
#include   
#include   
#include   
  
#define Fup(i, s, t) for (int i = s; i <= t; i ++)  
#define Fdn(i, s, t) for (int i = s; i >= t; i --)  
#define Path(i, s) for (int i = s; i; i = d[i].next)  
  
  
using namespace std;  
  
const int maxn = 200010;  
struct number {  
    int x;  
    int pos;  
} num[maxn];  
  
struct node {  
    int now;  
    int next;  
  
} d[maxn];  
  
int val[maxn][2];  
int c[maxn];  
int rank[maxn];  
int sa[maxn];  
int pos[maxn];  
int x[maxn];  
int n;  
  
int k;  
  
int h[maxn];  
int height[maxn];  
  
string S,s;  
  
int sta[maxn], num1[maxn], num2[maxn];  
bool cmp(const number& a, const number& b) {  
    return a.x < b.x;  
}  
  
void add_value(int u, int v, int i) {  
    d[i].next = c[u];  
    c[u] = i;  
    d[i].now = v;  
}  
  
void radix_sort(int l, int r) {  
    for (int k = 1; k >= 0; --k) {  
  
        memset(c, 0, sizeof(c));  
        for (int i = r; i >= l; --i) {  
            add_value(val[pos[i]][k], pos[i], i);  
        }  
        int t = 0;  
        for (int i = 0; i <= 200000; ++i) {  
            for (int j = c[i]; j; j = d[j].next) {  
                pos[++t] = d[j].now;  
            }  
        }  
    }  
    int t = 0;  
    for (int i = 1; i <= n; ++i) {  
        if (val[pos[i]][0] != val[pos[i - 1]][0]  
                || val[pos[i]][1] != val[pos[i - 1]][1]) {  
            t++;  
        }  
        rank[pos[i]] = t;  
    }  
}  
  
bool exist(int len) {  
    int now = 0;  
    int s = 0;  
    for (int i = 1; i <= n; ++i) { //枚举名次数组...  
        if (height[i] < len) {  
            s = max(s, now); //结束当前组  
            now = 1; //now恢复为1  
        } else {  
            now++;  
        }  
    }  
    s = max(s, now);  
  
    if (s >= k) {  
        return 1;  
    }  
    return 0;  
}  
  
void get_suffix_array() {  
    int t = 1;  
    while (t / 2 <= n) {  
        for (int i = 1; i <= n; ++i) {  
  
            val[i][0] = rank[i];  
            val[i][1] = (((i + t / 2 <= n)   rank[i + t / 2] : 0));  
            pos[i] = i;  
        }  
        radix_sort(1, n);  
        t *= 2;  
    }  
    for (int i = 1; i <= n; ++i) {  
        sa[rank[i]] = i;  
    }  
}  
  
void get_common_prefix() {  
    memset(h, 0, sizeof(h));  
    for (int i = 1; i <= n; ++i) {  
  
        if (rank[i] == 1) {  
            h[i] = 0;  
        } else {  
            int now = 0;  
            if (i >





 1 && h[i - 1] > 1) {  
                now = h[i - 1] - 1;  
            }  
            while (now + i <= n && now + sa[rank[i] - 1] <= n  
                    && x[now + i] == x[now + sa[rank[i] - 1]]) {  
                now++;  
            }  
            h[i] = now;  
        }  
    }  
    for (int i = 1; i <= n; ++i) {  
        height[rank[i]] = h[i];  
    }  
}  
  
int binary_search(int l, int r) {  
    while (l <= r) {  
        int mid = (l + r) / 2;  
        if (exist(mid)) {  
            l = mid + 1;  
        } else {  
            r = mid - 1;  
        }  
    }  
    return r;  
}  
  
void get_ans() {  
    Fup(i, 2, n)  
    height[i] -= k - 1;  
    long long sum1 = 0, sum2 = 0, ans = 0;  
    int top = 0;  
    Fup(i, 2, n)  
    if (height[i] <= 0) {  
        top = sum1 = sum2 = 0;  
    } else {  
        sta[++top] = height[i];  
        if (sa[i - 1] <= (int) S.size()) {  
            num1[top] = 1;  
            num2[top] = 0;  
            sum1 += (long long) sta[top];  
        } else {  
            num1[top] = 0;  
            num2[top] = 1;  
            sum2 += (long long) sta[top];  
        }  
        while (top > 0 && sta[top] <= sta[top - 1]) {  
            sum1 = sum1 - (long long) sta[top - 1] * num1[top - 1]  
                    + (long long) sta[top] * num1[top - 1];  
            sum2 = sum2 - (long long) sta[top - 1] * num2[top - 1]  
                    + (long long) sta[top] * num2[top - 1];  
            num1[top - 1] += num1[top];  
            num2[top - 1] += num2[top];  
            sta[top - 1] = sta[top];  
            top--;  
        }  
        if (sa[i] <= (int) S.size())  
            ans += sum2;  
        else  
            ans += sum1;  
    }  
    cout << ans << endl;  
}  
  
void init() {  
    cin >> S >> s;  
    n = (int) S.size() + s.size() + 1;  
    string str = S + '$' + s;  
    Fup(i, 1, n)  
    x[i] = rank[i] = (int) str[i - 1];  
}  
  
void solve() {  
    get_suffix_array();  
    get_common_prefix();  
    get_ans();  
}  
  
int main(){  
    while(scanf("%d",&k)!=EOF,k){  
        init();  
        solve();  
    }  
  
    return 0;  
}