题意
给定一个长度为n的小写字母串，让我们模拟以下过程 对于查询位置i，在[0,i)范围内寻找一个T使得从T开始的字串与从i开始的字串相等且最长。 找到输出
l
e
n
，
T
。
i
+
=
l
e
n
len，T。i+=len
len，T。i+=len 没找到输出
−
1
，
s
t
r
[
i
]
的
A
S
C
I
I
码
，
i
+
=
1
-1，str[i]的ASCII码，i+=1
−1，str[i]的ASCII码，i+=1
题解
对于每次询问，我们都从根节点出发走son字典树，查询是否匹配，若匹配则将该询问点插入自动机，继续匹配。不匹配则退出。因此只要记录到达每个状态的firstpos即可。
代码
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef double db
;
void _R(int &x
) { scanf("%d", &x
); }
void _R(ll
&x
) { scanf("%lld", &x
); }
void _R(db
&x
) { scanf("%lf", &x
); }
void _R(char &x
) { scanf(" %c", &x
); }
void _R(char *x
) { scanf("%s", x
+1); }
void R() {}
template<class T, class... U
> void R(T
&head
, U
&... tail
) { _R(head
); R(tail
...); }
void _W(const int &x
) { printf("%d", x
); }
void _W(const ll
&x
) { printf("%lld", x
); }
void _W(const db
&x
) { printf("%.16f", x
); }
void _W(const char &x
) { putchar(x
); }
void _W(const char *x
) { printf("%s", x
); }
template<class T> void _W(const vector
<T
> &x
) { for (auto i
= x
.begin(); i
!= x
.end(); _W(*i
++)) if (i
!= x
.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U
> void W(const T
&head
, const U
&... tail
) { _W(head
); putchar(sizeof...(tail
) ? ' ' : '\n'); W(tail
...); }
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define erp(x,y,z) for(int x=y;x>=z;x--)
#define PB push_back
#define MP make_pair
#define INF 1073741824
#define inf 1152921504606846976
#define pi 3.14159265358979323846
#define Fi first
#define Se second
const int N
=1e5+7,M
=2e6;
const long long mod
=1e9+7;
inline int read(){int ret
=0;char ch
=getchar();bool f
=1;for(;!isdigit(ch
);ch
=getchar()) f
^=!(ch
^'-');for(;isdigit(ch
);ch
=getchar()) ret
=(ret
<<1)+(ret
<<3)+ch
-48;return f
?ret
:-ret
;}
ll
gcd(ll a
,ll b
){return b
?gcd(b
,a
%b
):a
;}
ll
ksm(ll a
,ll b
,ll mod
){int ans
=1;while(b
){if(b
&1) ans
=(ans
*a
)%mod
;a
=(a
*a
)%mod
;b
>>=1;}return ans
;}
ll
inv2(ll a
,ll mod
){return ksm(a
,mod
-2,mod
);}
void TelmaZzzz(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
}
const int S
=26;
int tot
,last
,pre
[N
<<1],son
[N
<<1][S
],ml
[N
<<1],cnt
[N
<<1],firstpos
[N
<<1];
int now
[N
];
int len
,T
;
int res
[N
<<1];
char str
[N
];
queue
<int>q
;
vector
<int>E
[N
<<1];
int f
[N
<<1][22];
int newnod(){
tot
++;
for(int i
=0;i
<S
;i
++){
son
[tot
][i
]=0;
}
ml
[tot
]=0;
return tot
;
}
void extend(int w
){
int p
=newnod(),x
=last
,r
,q
;
for(ml
[last
=p
]=ml
[x
]+1;x
&&!son
[x
][w
];x
=pre
[x
]) son
[x
][w
]=p
;
firstpos
[tot
]=ml
[tot
]-1;
if(!x
) pre
[p
]=1;
else if(ml
[x
]+1==ml
[q
=son
[x
][w
]]) pre
[p
]=q
;
else {
pre
[r
=newnod()]=pre
[q
];
memcpy(son
[r
],son
[q
],sizeof son
[r
]);
ml
[r
]=ml
[x
]+1;pre
[p
]=pre
[q
]=r
;
for(;x
&&son
[x
][w
]==q
;x
=pre
[x
]) son
[x
][w
]=r
;
firstpos
[r
]=firstpos
[q
];
}
}
int n
;
int judge(int x
){
int now
=1;
int res
=0;
int T
;
while(x
<=n
&&son
[now
][str
[x
]-'a']){
now
=son
[now
][str
[x
]-'a'];
res
++;
T
=firstpos
[now
]-res
+1;
extend(str
[x
]-'a');
x
++;
}
if(res
==0){
printf("%d %d\n",-1,str
[x
]);
extend(str
[x
]-'a');
x
++;
}
else {
printf("%d %d\n",res
,T
);
}
return x
;
}
int main(){
TelmaZzzz();
int t
;
R(t
);
int ti
=0;
while(t
--){
R(str
);
n
=strlen(str
+1);
tot
=0;
last
=1;
newnod();
int zi
=1;
printf("Case #%d:\n",++ti
);
while(zi
<=n
){
zi
=judge(zi
);
}
}
return 0;
}
