G2. 唐纳德与子串 (Hard)
Time limit per test: 2.5 seconds
Memory limit: 512 megabytes
子串的定义是在一个字符串中连续出现的一段字符。这里，我们使用 s[l…r] 来表示 s 字符串从 l 到 r（闭区间）的子串。在本题中，字符串下标从 0 开始。显然，对于长度为 n 的字符串共有 n(n+1)2 个子串。
对于一个给定的字符串 s，唐纳德给出 q 次询问，第 i 次询问包括三个参数 li,ri,zi，问在 s[li…ri] 的所有子串***有多少个恰好为 zi。
Input
输入具有如下形式：
sql1 r1 z1l2 r2 z2⋮lq rq zq
第一行一个字符串 s。
第二行一个整数 q。
接下来每行：首先两个整数 li,ri (0≤li≤ri<|s|)，然后是一个非空字符串 zi。整数和整数，整数和字符串间以单空格隔开。
字符串中只会出现 26 个小写英文字母。
数据规模约定：
对于 Easy 档：1≤|s|≤100,q≤∑|zi|≤100。
对于 Hard 档：1≤|s|≤105,q≤∑|zi|≤105。
Output
对于每次询问，输出一个整数，表示答案。
/***********************************************/
考虑离线处理。将所有查询和母串相连建后缀数组。对于每一个查询，在排好序的后缀数组中恰好有一段相对应，可以二分求得 L,R。问题就转换为在 L,R 区间内有多少后缀的下标在查询区间范围内的。这是一个非常经典的区间问题。继续考虑离线处理，从大往小将数插入，然后使用树状数组轻松解决。时间复杂度 O(nlogn)。
事实上本题的做法非常套路，所以过得人也比 F 多（？？？）。
据验题人说暴力加疯狂特判也能过，而且玄学优化不可卡。暴力姿势太大，比不来。
/***********************************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N= 1000100;
const int M = 25000100;
vector<int>T[N];
vector<int>stop[N];
int rt[N],L[M],R[M];
int sum[M],id;
int n,m,q;
int ql,qr,ed;
char a[N>>1];
ll ans = 0;
struct SAM
{
int son[N][26],step[N],f[N],tot,last;
SAM(){tot=last=1;}
void insert(int ch)
{
int np=++tot,p,q;
step[np]=step[last]+1;
for (p=last;p&&!son[p][ch];p=f[p]) {
son[p][ch]=np;
}
last=np;
if (!p){
f[np]=1;return;
}
if (step[q=son[p][ch]]==step[p]+1)
{
f[np]=q;return;
}
int nq=++tot;
step[nq]=step[p]+1;
memcpy(son[nq],son[q],sizeof(son[q]));
f[nq]=f[q];
f[np]=f[q]=nq;
for (;p&&son[p][ch]==q;p=f[p])
{
son[p][ch]=nq;
}
}
void init(){
int t=1;
for (int i=0;i<n;i++){
stop[t=son[t][a[i]-'a']].push_back(i+1);
}
for (int i=2;i<=tot;i++){
T[f[i]].push_back(i);
}
}
}sam;
void update(int &x,int l,int r,int pos)
{
int y=x;
x=++id;
sum[x]=sum[y]+1;
L[x]=L[y];R[x]=R[y];
if (l==r) return;
int mid=(l+r)>>1;
if (pos<=mid) update(L[x],l,mid,pos);
else update(R[x],mid+1,r,pos);
}
int combine(int x,int y,int l,int r)
{
if (x==0||y==0) return x+y;
int res=++id;
int mid=(l+r)>>1;
sum[res]=sum[x]+sum[y];
L[res]=combine(L[x],L[y],l,mid);
R[res]=combine(R[x],R[y],mid+1,r);
return res;
}
void dfs(int x)
{
for (int i=0;i<stop[x].size();i++){
update(rt[x],1,n,stop[x][i]);
}
for (int i=0;i<T[x].size();i++){
int y=T[x][i];
dfs(y);
rt[x]=combine(rt[x],rt[y],1,n);
}
}
int query(int x,int l,int r)
{
if (ql<=l && r<=qr || x==0) return sum[x];
int mid=(l+r)>>1;
int ans=0;
if (ql<=mid) ans+=query(L[x],l,mid);
if (qr>mid) ans+=query(R[x],mid+1,r);
return ans;
}
int main(int argc, char const *argv[]) {
scanf("%s",a);
n=strlen(a);
for (int i=0;i<n;i++){
sam.insert(a[i]-'a');
}
sam.init();
dfs(1);
scanf("%d",&q);
while (q--)
{
scanf("%d%d",&ql,&qr);
++ql;++qr;
scanf("%s",a);
m=strlen(a);
ql=ql+m-1;
int t=1;
for(int i=0;i < m && t;i++){
t=sam.son[t][a[i]-'a'];
}
printf("%d\n",query(rt[t],1,n));
}
return 0;
}#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
string st;
const int N = 2000000;
struct opt
{
int i, v;
string t;
};
vector <opt> V[N];
int q;
int ans[N];
#define lc t[x].ch[0]
#define rc t[x].ch[1]
#define pa t[x].fa
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
}
struct Node{
int ch[2],fa,w,add;
}t[N];
inline int isR(int x){return t[pa].ch[0]!=x&&t[pa].ch[1]!=x;}
inline int wh(int x){return t[pa].ch[1]==x;}
inline void paint(int x,int d){t[x].add+=d;t[x].w+=d;}
inline void pushDown(int x){
if(t[x].add){
paint(lc,t[x].add);
paint(rc,t[x].add);
t[x].add=0;
}
}
inline void rotate(int x){
int f=t[x].fa,g=t[f].fa,c=wh(x);
if(!isR(f)) t[g].ch[wh(f)]=x;t[x].fa=g;
t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f;
t[x].ch[c^1]=f;t[f].fa=x;
}
inline void pd(int x){
if(!isR(x)) pd(t[x].fa);
pushDown(x);
}
inline void splay(int x){
pd(x);
for(;!isR(x);rotate(x))
if(!isR(pa)) rotate(wh(x)==wh(pa)?pa:x);
}
inline void Access(int x){
for(int y=0;x;y=x,x=pa)
splay(x),rc=y;
}
inline void Link(int x,int y){
t[x].fa=y;
Access(y);splay(y);paint(y,t[x].w);
}
inline void Cut(int x){
Access(x);splay(x);paint(lc,-t[x].w);
t[lc].fa=0;lc=0;
//update(y);
}
inline void SetW(int x,int v){t[x].w=v;}
inline int GetW(int x){return t[x].w;}
int n,Q;
char s[N],op[20];
struct SAM{
struct State{
int ch[26],val,par;
}t[N];
int sz,root,last;
inline int nw(int _){t[++sz].val=_;return sz;}
inline void iniSAM(){sz=0;root=last=nw(0);}
void extend(int c){
int p=last,np=nw(t[p].val+1); SetW(np,1);
while(p&&!t[p].ch[c]) t[p].ch[c]=np,p=t[p].par;
if(!p) t[np].par=root, Link(np,root);
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+1) t[np].par=q, Link(np,q);
else{
int nq=nw(t[p].val+1);
memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));
t[nq].par=t[q].par;
Link(nq,t[q].par);
t[q].par=t[np].par=nq;
Cut(q);Link(q,nq);Link(np,nq);
while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].par;
}
}
last=np;
}
int Query(){
int u=root;
for(int i=0;i<n;i++){
int c=s[i]-'a';
if(t[u].ch[c]) u=t[u].ch[c];
else return 0;
}
pd(u);//!!
splay(u);
return GetW(u);
}
void Insert(char c){
extend(c-'a');
}
}sam;
int main()
{
// freopen("G2.in", "r", stdin);
ios :: sync_with_stdio(0);
cin >> st;
cin >> q;
sam.iniSAM();
for (int i = 1; i <= q; ++ i)
{
int l, r; string t;
cin >> l >> r >> t;
V[r].push_back((opt){i, 1, t});
if (l + (int)t.length() - 2 >= 0)
V[l + (int)t.length() - 2].push_back((opt){i, -1, t});
}
for (int i = 0; i < st.length(); ++ i)
{
sam.Insert(st[i]);
for (int j = 0; j < V[i].size(); ++ j)
{
n = V[i][j].t.size();
for (int k = 0; k < n; ++ k)
s[k] = V[i][j].t[k];
int _=sam.Query();
ans[V[i][j].i] += _ * V[i][j].v;
}
}
for (int i = 1; i <= q; ++ i)
cout << ans[i] << endl;
}#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int r[maxn<<1];
namespace LCT {
int tr[maxn<<1][2],fa[maxn<<1],tag[maxn<<1];
void pushdown(int x) {
if (tr[fa[x]][0]==x || tr[fa[x]][1]==x) pushdown(fa[x]);
if (tag[x]) {
r[tr[x][0]]+=tag[x];tag[tr[x][0]]+=tag[x];
r[tr[x][1]]+=tag[x];tag[tr[x][1]]+=tag[x];
tag[x]=0;
}
}
void rotate(int x) {
int y=fa[x],z=fa[y],l,r;
l=tr[y][1]==x;r=l^1;
if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
tr[y][l]=tr[x][r];tr[x][r]=y;
}
void splay(int x) {
pushdown(x);
while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) {
int y=fa[x],z=fa[y];
if (tr[z][0]==y || tr[z][1]==y) {
if (tr[z][0]==y ^ tr[y][0]==x) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x) {
for (int y=0;x;y=x,x=fa[x])
splay(x),tr[x][1]=y;
}
void add(int x,int val) {
r[x]+=val;tag[x]+=val;
}
void link(int x,int y) {
access(y);splay(y);add(y,r[x]);
fa[x]=y;
}
void cut(int x) {
access(x);splay(x);add(tr[x][0],-r[x]);
tr[x][0]=fa[tr[x][0]]=0;
}
int query(int x) {
splay(x);return r[x];
}
}
using namespace LCT;
struct SAM {
const static int SZ = 26;
char a = 'a';
struct state {
int max, fa, go[SZ];
};
vector<state> st;
int last = 1, num = 2; // 0 is NULL, 1 is empty string
SAM(int n) { st.resize(2 * n + 10); }
SAM(const string& s, int n) : SAM(n) { for (auto i : s) push_back(i); }
void push_back(char ch) {
int c = ch - a;
int now = last;
last = num++;
r[last] = 1;
st[last] = {st[now].max + 1, 1};
while (now && !st[now].go[c]) st[now].go[c] = last, now = st[now].fa;
if (now) {
int nex = st[now].go[c];
if (st[now].max + 1 == st[nex].max) st[last].fa = nex, link(last, nex);
else {
st[num] = st[nex];
st[num].max = st[now].max + 1;
link(num, st[num].fa);
st[last].fa = st[nex].fa = num;
cut(nex), link(last, num), link(nex, num);
while (now && st[now].go[c] == nex) st[now].go[c] = num, now = st[now].fa;
num++;
}
} else link(last, 1);
}
vector<int> topsort() {
int len = st[last].max + 1;
vector<int> cnt(len), res(num);
for (int i = 1; i < num; i++) cnt[st[i].max]++;
for (int i = 1; i < len; i++) cnt[i] += cnt[i - 1];
for (int i = 1; i < num; i++) res[cnt[st[i].max]--] = i;
return res;
}
int sum(size_t x) { return query(x); }
};
struct Que {
int idx, num, typ;
string s;
bool operator< (const Que& e) const {
return idx < e.idx;
};
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
SAM sam(s.length());
int q;
cin >> q;
vector<Que> xw(2 * q);
for (int i = 0; i < q; i++) {
int l, r;
string t;
cin >> l >> r >> t;
xw[2 * i] = {l + t.length() - 1, i, 0, t};
xw[2 * i + 1] = {r + 1, i, 1, t};
}
sort(xw.begin(), xw.end());
int now = 0;
vector<int> ans(q);
for (auto& i : xw) {
while (now < s.length() && now < i.idx) {
sam.push_back(s[now]);
now++;
}
int tmp = 1;
for (auto j : i.s) {
tmp = sam.st[tmp].go[j - 'a'];
if (!tmp) break;
}
if (tmp) {
if (i.typ) ans[i.num] += sam.sum(tmp);
else ans[i.num] -= sam.sum(tmp);
}
}
for (auto i : ans) cout << i << '\n';
}后缀数组官方题解版
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
const int Nlog = 20;
struct SuffixArray {
const int L;
vector<vector<int> > P;
vector<pair<pair<int, int>, int> > M;
int s[N], sa[N], rank[N], height[N];
// s: raw string
// sa[i]=k: s[k...L-1] ranks i (0 based)
// rank[i]=k: the rank of s[i...L-1] is k (0 based)
// height[i] = lcp(sa[i-1], sa[i])
SuffixArray(const string &raw_s) : L(raw_s.length()), P(1, vector<int>(L, 0)), M(L) {
for (int i = 0; i < L; i++)
P[0][i] = this->s[i] = int(raw_s[i]);
for (int skip = 1, level = 1; skip < L; skip *= 2, level++) {
P.push_back(vector<int>(L, 0));
for (int i = 0; i < L; i++)
M[i] = make_pair(make_pair(P[level - 1][i], i + skip < L ? P[level - 1][i + skip] : -1000), i);
sort(M.begin(), M.end());
for (int i = 0; i < L; i++)
P[level][M[i].second] = (i > 0 && M[i].first == M[i - 1].first) ? P[level][M[i - 1].second] : i;
}
for (unsigned i = 0; i < P.back().size(); ++i) {
rank[i] = P.back()[i];
sa[rank[i]] = i;
}
}
// This is a traditional way to calculate LCP
void getHeight() {
memset(height, 0, sizeof height);
int k = 0;
for (int i = 0; i < L; ++i) {
if (rank[i] == 0) continue;
if (k) k--;
int j = sa[rank[i] - 1];
while (i + k < L && j + k < L && s[i + k] == s[j + k]) ++k;
height[rank[i]] = k;
}
rmq_init(height, L);
}
int f[N][Nlog];
inline int highbit(int x) {
return 31 - __builtin_clz(x);
}
int rmq_query(int x, int y) {
int p = highbit(y - x + 1);
return min(f[x][p], f[y - (1 << p) + 1][p]);
}
// arr has to be 0 based
void rmq_init(int *arr, int length) {
for (int x = 0; x <= highbit(length); ++x)
for (int i = 0; i <= length - (1 << x); ++i) {
if (!x) f[i][x] = arr[i];
else f[i][x] = min(f[i][x - 1], f[i + (1 << (x - 1))][x - 1]);
}
}
int LongestCommonPrefix(int i, int j) {
// getHeight() must be called first
if (i == j) return L - i;
if (i > j) swap(i, j);
return rmq_query(i + 1, j);
}
int leftBound(int x, int len) {
x = rank[x];
int l = 0, r = x;
while (l < r) {
int mid = (l + r) / 2;
if (LongestCommonPrefix(mid, x) < len)
l = mid + 1;
else r = mid;
}
return l;
}
int rightBound(int x, int len) {
x = rank[x];
int l = x, r = L - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (LongestCommonPrefix(mid, x) < len)
r = mid - 1;
else l = mid;
}
return l;
}
} *S;
struct BIT {
int c[N];
void init() {
memset(c, 0, sizeof c);
}
void add(int x, int d) {
x++;
while (x < N) {
c[x] += d;
x += x & -x;
}
}
int sum(int x) {
x++;
int ret = 0;
while (x) {
ret += c[x];
x -= x & -x;
}
return ret;
}
int sum(int l, int r) {
if (r < l) return 0;
return sum(r) - sum(l - 1);
}
} bit;
struct Query {
int qn, ql, l, r, sa_l, sa_r, id;
vector<int> ans;
};
struct Event {
int l, r, time, pos, type, id;
// type=1 insert
// type=2 query
bool operator < (const Event &e) const {
return time < e.time || (time == e.time && type < e.type);
}
};
string mother;
int q;
Query d[N];
vector<Event> events;
int main() {
cin >> mother >> q;
for (int i = 0; i < q; ++i) {
string str;
d[i].id = i;
cin >> d[i].l >> d[i].r >> str;
d[i].qn = mother.length();
d[i].ql = str.length();
mother += str;
}
S = new SuffixArray(mother);
S->getHeight();
// for (int i = 0; i < S->L; ++i)
// cout << i << " " << mother.substr(S->sa[i]) << endl;
for (int i = 0; i < q; ++i) {
d[i].sa_l = S->leftBound(d[i].qn, d[i].ql);
d[i].sa_r = S->rightBound(d[i].qn, d[i].ql);
// printf("%d %d\n", d[i].sa_l, d[i].sa_r);
}
for (int i = 0; i < q; ++i) {
events.push_back((Event){d[i].sa_l, d[i].sa_r, d[i].l - 1, 0, 2, i});
events.push_back((Event){d[i].sa_l, d[i].sa_r, d[i].r - d[i].ql + 1, 0, 2, i});
}
for (int i = 0; i < S->L; ++i)
events.push_back((Event){0, 0, S->sa[i], i, 1, i});
sort(events.begin(), events.end());
for (Event e: events) {
if (e.type == 1) {
bit.add(e.pos, 1);
} else {
d[e.id].ans.push_back(bit.sum(e.l, e.r));
}
}
for (int i = 0; i < q; ++i) {
assert (d[i].ans.size() == 2);
int a = d[i].ans[1] - d[i].ans[0];
assert (a >= 0);
printf("%d\n", a);
}
}Easy版code:
#include<stdio.h>
#include<string.h>
#include<string>
char s[1005],h[1005];
int next[1005];
int q,l,r,n;
void get_next()///求得模式串的next数组
{
next[0] = -1;
int k = -1;
for (int i = 1; i < n; i++)
{
while (k > -1 && h[k + 1] != h[i])
{
k = next[k];
}
if (h[k + 1] == h[i])
{
k = k + 1;
}
next[i] = k;
}
}
int KMP()///进行匹配
{
get_next();
int k = -1;
int sum=0;
for (int i = l; i <= r; i++ )
{
while (k >-1&& h[k + 1] != s[i])
{
k = next[k];
}
if (h[k + 1] == s[i])
k = k + 1;
if (k == n-1)
{
sum++;
}
}
return sum;
}
int main()
{
int ans;
scanf("%s",s);
scanf("%d",&q);
while(q--)
{
scanf("%d %d %s",&l,&r,h);
n=strlen(h);
ans=KMP();
printf("%d\n",ans);
}
return 0;
} #include<stdio.h>
#include<string.h>
int main(void)
{
char s[100000],z[100000];
int q;
scanf("%s",s);
scanf("%d",&q);
int i,j,k,savei;
int l,r,count;
int lson;
for(k=0;k<q;k++)
{
count=0;
scanf("%d %d %s",&l,&r,z);
lson=strlen(z);
for(i=l;i<=r;i++)
{
j=0;
savei=i;
while(s[savei]==z[j]&&savei<=r&&lson<=(r-l+1)&&j<lson)
{
savei++;
j++;
}
if(j==lson)
count++;
}
printf("%d\n",count);
}
}#include <iostream>
#include <string>
using namespace std;
int main()
{
int q,l,r;
string s,z;
cin>>s;
cin>>q;
while(q--){
cin>>l>>r;
cin>>z;
string a=s.substr(l,r-l+1);
int p=0,i=0;
while(( p=a.find(z,p))!=-1){
p++;
i++;
}
cout<<i<<endl;
}
return 0;
} #include<iostream>
using namespace std;
int main()
{
string s;
cin>>s;
int q;
cin>>q;
while(q--)
{
int a,b,count=0;
cin>>a>>b;
string str1;
cin>>str1;
int leng = str1.length();
for(int i=a;i+leng-1<=b;i++)
{
if(s.substr(i,leng)==str1)count++;
}
cout<<count<<endl;
}
}#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)
const LL maxn = 110;
char s[maxn], s2[maxn];
LL q, l1, l2;
int main() {
scanf("%s%lld", s, &q); l1 = strlen(s);
FOR (_, 0, q) {
LL l, r; scanf("%lld%lld%s", &l, &r, s2);
LL l2 = strlen(s2);
LL ans = 0;
if (l2 <= r - l + 1) {
for (LL i = l; i + l2 - 1 <= r; ++i) {
bool flag = true;
FOR (j, 0, l2)
if (s2[j] != s[i + j]) { flag = false; break; }
if (flag) ++ans;
}
}
printf("%lld\n", ans);
}
}#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
char s[105] = { 0 };
int q;
int l, r;
char z[105] = { 0 };
scanf("%s", s);
scanf("%d", &q);
int i, j, k;
for (i = 0; i < q; i++)
{
scanf("%d%d%s", &l, &r, z);
int len = strlen(z);
int flag = 0;
for (j = l; j <= r - len+1; j++)
{
if (strncmp(s+j, z, len) == 0)
flag++;
}
printf("%d\n", flag);
}
return 0;
}my_code
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
char s[900],ss[200];
unsigned int h[2000],h2[200],base[200];
inline void init_hash(int l,char *s,unsigned int*h)
{
h[0] = 0;
for(int i=1;i<=l;i++)
h[i] = h[i-1]*131+s[i-1];
base[0] = 1;
for(int i=1;i<=l;i++)
base[i] = base[i-1]*131;
}
inline unsigned int str(unsigned int*h,int l,int r)
{
return h[r]-h[l]*base[r-l];
}
int main()
{
cin>>s;
init_hash(200,s,h);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
unsigned int p1 = str(h,l,r);
// cout<<p1<<endl;
cin>>ss;
int len = strlen(ss);
init_hash(len,ss,h2);
unsigned int p2 = str(h2,0,len);
//cout<<p2<<endl;
int sum = 0;
for(int ii=l;ii<=r+1;ii++)
{
for(int j=ii+1;j<=r+1;j++)
{
unsigned int p1 = str(h,ii,j);
if(p1==p2)sum++;
}
}
cout<<sum<<endl;
}
return 0;
}my_code2
#include <iostream>
#include <cstring>
using namespace std;
int l,r,p,sum;
int next1[100000];
string s,z;
void gtnext()
{
int k=-1,j=0;
next1[0]=-1;
while(j<z.size())
{
if(k==-1||z[j]==z[k])
{
j++;
k++;
if(z[j]!=z[k])
next1[j]=k;
else
next1[j]=next1[k];
}
else
k=next1[k];
}
}
int kmp()
{
int j=l,k=0;
while(j<=r)
{
if(k==-1||s[j]==z[k])
{
j++;
k++;
}
else
k=next1[k];
if(k==z.size())
{
sum++;
k=next1[k];
}
}
cout<<sum<<endl;
}
int main()
{
cin>>s;
cin>>p;
for(int i=0;i<p;++i)
{
sum=0;
cin>>l>>r;
cin>>z;
memset(next1,0,sizeof(next1));
gtnext();
kmp();
}
return 0;
}
京公网安备 11010502036488号