描述
题解
给定一个长度不超过 10W 的只包含小写字母的字符串,从下标 0 到
从下标 0 开始操作,
每次对于下标
其他出现的位置要求起点在位置 pos 之前,然后 pos 移动到这个长度之后继续操作;
如果没有这样的最长串儿就直接 pos++ ,继续操作,直到 pos=n 结束。
对于上述两种操作,前者输出最大长度 K 以及这种串儿最左边出现的位置;
后者输出
典型的后缀自动机问题,询问位置 pos 开始的后缀和位置 0∼pos−1 开始的所有后缀的最大匹配的公共前缀长度。
每次询问 pos 位置的时候,一边向后匹配一个位置一边将那个位置加入后缀自动机即可,一边匹配一边加入,可以保证询问位置 pos 的时候, pos−1 位置能提供最大的长度是可以保证的。匹配的操作是从当前后缀自动机的根节点向后遍历,只要从当前节点向下的 go 指针非空即说明之前有这样的串儿。
参考博客:Gatevin’s blog
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXM = 2e5 + 10;
const int MAXN = 1e5 + 10;
const int MAGIC = 26;
struct Suffix_Automation
{
struct State
{
State *par;
State *go[MAGIC];
int val;
int mi;
int cnt;
int right;
int leftmost;
void init(int _val = 0)
{
par = 0;
val = _val;
cnt = 0;
mi = 0;
right = 0;
leftmost = 1e9;
memset(go, 0, sizeof(go));
}
};
State *root, *last, *cur;
State nodePool[MAXM];
State *newState(int val = 0)
{
cur->init(val);
return cur++;
}
void initSAM()
{
cur = nodePool;
root = newState();
last = root;
}
void extend(int w, int head)
{
State *p = last;
State *np = newState(p->val + 1);
np->right = 1;
np->leftmost = head;
while (p && p->go[w] == 0)
{
p->go[w] = np;
p = p->par;
}
if (p == 0)
{
np->par = root;
}
else
{
State *q = p->go[w];
if (p->val + 1 == q->val)
{
np->par = q;
}
else
{
State *nq = newState(p->val + 1);
memcpy(nq->go, q->go, sizeof(q->go));
nq->leftmost = q->leftmost;
nq->par = q->par;
q->par = nq;
np->par = nq;
while (p && p->go[w] == q)
{
p->go[w] = nq;
p = p->par;
}
}
}
last = np;
}
void solve(char *s)
{
initSAM();
int n = (int)strlen(s);
int now = 0;
while (now != n)
{
State *pos = root;
int deep = 0;
while (now < n && pos->go[s[now] - 'a'] != 0)
{
pos = pos->go[s[now] - 'a'];
deep++;
extend(s[now] - 'a', now);
now++;
}
if (deep == 0)
{
extend(s[now] - 'a', now);
printf("-1 %d\n", s[now++]);
}
else
{
printf("%d %d\n", deep, pos->leftmost - deep + 1);
}
}
}
};
Suffix_Automation sam;
char s[MAXN];
int main()
{
int T;
scanf("%d", &T);
for (int case_ = 1; case_ <= T; case_++)
{
printf("Case #%d:\n", case_);
scanf("%s", s);
sam.solve(s);
}
return 0;
}