首页 > 代码库 > POJ 3415
POJ 3415
一道字符串的题。
求两个字符串的长度大于K的子串中，相同的有多少对。
知道了要用到后缀数组，可是想了好久也没想好怎么使用。最后看了一下论文，提到了两个字符串可以合并，中间加上一个特殊字符就可以了。|
虽然这样还是写了好长时间啊。。。
首先是合并，然后建立后缀数组，求出sa[]，height[]，然后在进行加和，用到了一个题解称作单调栈的东西。不知是什么，反正就是合并嘛。
分别对于两个串进行加和。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define maxn 200010#define LL long longint rank[maxn], sa[maxn], t1[maxn], t2[maxn], sum[maxn], h[maxn];char c[maxn];void solve(){ int *x = t1; int *y = t2; int m = 128; int l = strlen(c); for(int i = 0; i < m; i++) sum[i] = 0; for(int i = 0; i <= l; i++) sum[x[i]=c[i]]++; for(int i = 1; i < m; i++) sum[i] += sum[i-1]; for(int i = l; i >= 0; i--) sa[--sum[x[i]]] = i; for(int j = 1; j <= l; j <<= 1) { int num = 0; for(int i = l-j+1; i<=l; i++) y[num++] = i; for(int i = 0; i <= l; i++) if(sa[i] >= j) y[num++] = sa[i] - j; for(int i = 0; i < m; i++) sum[i] = 0; for(int i = 0; i <= l; i++) sum[x[i]]++; for(int i = 1; i < m; i++) sum[i] += sum[i-1]; for(int i = l; i >= 0; i--) sa[--sum[x[y[i]]]] = y[i]; swap(x,y); m = 1; x[sa[0]] = 0; for(int i = 1; i <= l; i++) x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+j] == y[sa[i-1]+j]) ? m-1:m++; if(m > l) break; } m = 0; for(int i = 0; i <= l; i++) rank[sa[i]] = i; for(int i = 0; i < l; i++) { if(m) m--; int j = sa[rank[i]-1]; while(c[i+m] == c[j+m]) m++; h[rank[i]] = m; }}int main(){ //freopen("in.txt", "r", stdin); //freopen("out(2).txt", "w", stdout); int n; while(scanf("%d", &n) && n) { scanf("%s", c); int l1 = strlen(c); c[l1] = 1; scanf("%s", c+l1+1); int l2 = strlen(c); c[l2] = 0; solve(); LL ans = 0; LL sum2 = 0; int l = 0; for(int i = 1; i <= l2; i++) { if(h[i] < n) { l = 0; sum2 = 0; } else { int tmp = 0; while(l && t1[l-1] >= h[i]) { l--; tmp += t2[l]; sum2 -= t2[l] * (t1[l] - h[i]); } t1[l] = h[i]; t2[l++] = tmp; if(sa[i-1] > l1) { t2[l-1]++; sum2 += h[i]- n + 1; } if(sa[i] < l1) ans += sum2; } } l = 0; sum2 = 0; for(int i = 1; i <= l2; i++) { if(h[i] < n) { l = 0; sum2 = 0; } else { int tmp = 0; while(l && t1[l-1] >= h[i]) { l--; tmp += t2[l]; sum2 -= t2[l] * (t1[l] - h[i]); } t1[l] = h[i]; t2[l++] = tmp; if(sa[i-1] < l1) { t2[l-1]++; sum2 += h[i] - n + 1; } if(sa[i] > l1) ans += sum2; } } cout << ans << endl; }}
这样的话对于求最长回文字串我也会了。。。
不过是将第二个串换成是它的逆序，然后找到最长的
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。