【POJ】3415 Common Substrings

时间:2022-04-21 21:21:00

后缀数组可解。使用单调栈优化。

 /* 3415 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxl = 1e5+;
const int maxn = maxl * ;
char as[maxl], bs[maxl];
int a[maxn];
int rank[maxn], height[maxn], sa[maxn];
int wa[maxn], wb[maxn], wc[maxn], wv[maxn];
int S[maxn][];
int K; bool cmp(int *r, int a, int b, int l) {
return r[a]==r[b] && r[a+l]==r[b+l];
} void da(int *r, int *sa, int n, int m) {
int i, j, *x=wa, *y=wb, *t, p; for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[x[i]=r[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) sa[--wc[x[i]]] = i;
for (j=,p=; p<n; j*=, m=p) {
for (p=,i=n-j; i<n; ++i) y[p++] = i;
for (i=; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i=; i<n; ++i) wv[i] = x[y[i]];
for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[wv[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) sa[--wc[wv[i]]] = y[i];
for (t=x,x=y,y=t, x[sa[]]=, p=, i=; i<n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p-:p++;
}
} void calheight(int *r, int *sa, int n) {
int i, j, k = ; for (i=; i<=n; ++i) rank[sa[i]] = i;
for (i=; i<n; height[rank[i++]]=k)
for (k?k--:, j=sa[rank[i]-]; r[i+k]==r[j+k]; ++k);
} void printSa(int n) {
for (int i=; i<=n; ++i)
printf("%d ", sa[i]);
putchar('\n');
} void printHeight(int n) {
for (int i=; i<=n; ++i)
printf("%d ", height[i]);
putchar('\n');
} void solve() {
int n = , nn; for (int i=; ; ++i) {
if (as[i] == '\0') {
nn = i;
break;
}
a[n++] = as[i];
}
a[n++] = ;
for (int i=; ; ++i) {
if (bs[i] == '\0') {
break;
}
a[n++] = bs[i];
}
a[n] = ; da(a, sa, n+, );
calheight(a, sa, n); int top;
__int64 tot, ans = ; // handle as with bs
top = ;
tot = ;
rep(i, , n+) {
if (height[i] < K) {
top = ;
tot = ;
} else {
int cnt = ;
if (sa[i-] < nn) {
++cnt;
tot += height[i] - K + ;
}
while (top && height[i]<=S[top-][]) {
--top;
tot -= 1LL * S[top][] * (S[top][] - height[i]);
cnt += S[top][];
}
S[top][] = height[i];
S[top][] = cnt;
++top;
if (sa[i] > nn)
ans += tot;
}
} tot = ;
top = ;
rep(i, , n+) {
if (height[i] < K) {
tot = ;
top = ;
} else {
int cnt = ;
if (sa[i-] > nn) {
++cnt;
tot += height[i] - K + ;
}
while (top && height[i]<=S[top-][]) {
--top;
tot -= 1LL * S[top][] * (S[top][] - height[i]);
cnt += S[top][];
}
S[top][] = height[i];
S[top][] = cnt;
++top;
if (sa[i] < nn)
ans += tot;
}
} printf("%I64d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%d", &K)!=EOF && K) {
scanf("%s%s", as, bs);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}

数据发生器。

 from random import randint, shuffle
import shutil
import string def GenDataIn():
with open("data.in", "w") as fout:
t = 20
bound = 10**2
lc = list(string.lowercase)
for tt in xrange(t):
k = randint(1, 10)
fout.write("%d\n" % (k))
length = randint(100, 500)
line = ""
for i in xrange(length):
idx = randint(0, 25)
line += lc[idx]
fout.write("%s\n" % line)
length = randint(100, 500)
line = ""
for i in xrange(length):
idx = randint(0, 25)
line += lc[idx]
fout.write("%s\n" % line)
fout.write("0\n") def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()