字符串-后缀|BZOJ 2865 字符串识别
后缀自动机+线段树
考虑最终包含点i的仅出现一次的子串长什么样。记这个子串是[l,r]。
l < i < r ： 即i不碰到左右端点，对于这种情况，可以暴力在SAM上找出所有出现一次的串，用线段树更新答案。
l = i ≤ r ： 设以r为右端点的出现一次的最短的串为[l’,r]，显然要有l≤l’。于是依然可以暴力找出所有出现一次的串，用r来更新[1,l-1]的答案。
【字符串-后缀|BZOJ 2865 字符串识别】l ≤ i = r ： 设以r为右端点的出现一次的最短的串为[l’,r]，显然要有l=l’，所以这种情况等价于第一种。
所以只需要两棵线段树。本题用SAM会被卡内存，SAM的大小适当开小一点即可。。。
#include
#include
#define N 500003
#define M 850003
#define A 26
#define cmin(u,v) (u)>(v)?(u)=(v):0
using namespace std;
namespace runzhe2000
{
const int INF = 1<<29;
int n, sum[N], ans[N];
char s[N];
struct SAM
{
SAM *next[A], *fail;
int len, right;
}mem[M], *tot, *null, *root, *last, *pos[M];
SAM* newnode(int len)
{
SAM *p = ++tot;
*p = *null;
p->len = len;
return p;
}
void init()
{
null = tot = mem;
for(int i = 0;
i < A;
i++) null->next[i] = null;
null->fail = null;
null->len = null->right = 0;
last = root = newnode(0);
}
void insert(int v)
{
SAM *np = newnode(last->len + 1), *p = last;
last = np;
np->right = 1;
for(;
p != null && p -> next[v] == null;
p = p->fail) p->next[v] = np;
if(p == null) np->fail = root;
else
{
SAM *q = p->next[v];
if(p->len + 1 == q->len) np->fail = q;
else
{
SAM *nq = newnode(0);
*nq = *q;
nq->len = p->len + 1;
nq -> right = 0;
// attention
q->fail = np->fail = nq;
for(;
p != null && p->next[v] == q;
p = p->fail) p->next[v] = nq;
}
}
}struct segment_tree
{
struct node {int val;
}t[N*5];
void build(int x, int l, int r)
{
t[x].val = INF;
if(l == r)return;
int mid = (l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void modi(int x, int l, int r, int ql, int qr, int val)
{
if(ql <= l && r <= qr) {cmin(t[x].val, val);
return;
}
int mid = (l+r)>>1;
if(ql <= mid) modi(x<<1,l,mid,ql,qr,val);
if(mid < qr) modi(x<<1|1,mid+1,r,ql,qr,val);
}
void pushall(int x, int l, int r, int val)
{
cmin(val, t[x].val);
if(l == r){cmin(ans[l], val);
return;
}
int mid = (l+r)>>1;
pushall(x<<1,l,mid,val);
pushall(x<<1|1,mid+1,r,val);
}
}t1,t2;
void main()
{
scanf("%s",s+1);
n = strlen(s+1);
init();
for(int i = 1;
i <= n;
i++)
insert(s[i] - 'a');
t1.build(1,1,n);
t2.build(1,1,n);
int cnt = tot - mem;
for(SAM *i = tot;
i != mem;
i--) sum[i->len]++;
for(int i = 1;
i <= n;
i++) sum[i] += sum[i-1];
for(SAM *i = tot;
i != mem;
i--) pos[sum[i->len]--] = i;
for(int i = cnt;
i;
i--)
{
SAM *p = pos[i];
if(p == root) continue;
p->fail->right += p->right;
if(p->right == 1)
{
int l = p->len - p->fail->len , r = p->len;
if(1 <= l-1)t1.modi(1,1,n,1,l-1,r);
t2.modi(1,1,n,l,r,r-l+1);
}
}
memset(ans,63,sizeof(ans));
t1.pushall(1,1,n,INF);
for(int i = 1;
i <= n;
i++) ans[i] = ans[i] - i + 1;
t2.pushall(1,1,n,INF);
for(int i = 1;
i <= n;
i++) printf("%d\n",ans[i]);
}
}
int main()
{
runzhe2000::main();
} 推荐阅读
- 一起来学习C语言的字符串转换函数
- 字符串拼接成段落，换行符（\n）如何只执行n-1次
- C语言的版本比较
- JavaScript|JavaScript — call()和apply()、Date对象、Math、包装类、字符串的方法
- JS截取字符串的方法详解
- Python|Python 字符串 子串 回文串
- LeetCode|LeetCode 每日一题 [52] 表示数值的字符串
- Swift|Swift 字符串转数组
- 关于ajax异步分页传输数据到页面为字符串的JS解决办法
- Python实用技法第33篇（字符串连接及合并）