代码

/*pragram by mangoyang*/
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<vector>
#include<cstring>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int f = 0, ch = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 3500005;
ll ans, n, all;
char s[N]; int Q;
struct SuffixAutomaton{
	vector<int> g[N], v;
	ll dep[N], sz[N], dd[N];
	int ch[N][26], fa[N], tail, size;
	inline SuffixAutomaton(){ size = tail = 1; }
	inline int newnode(int x){ return dep[++size] = x, size; }
    inline void ins(int c, int ff, int pos){
        int p = tail, np = newnode(dep[p] + 1);
        if(!ff){
        	sz[np] = 1;
        	Seg.ins(rt[u], 1, 1, n, pos); 
        }else v.push_back(np);
        
        for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
        if(!p) return (void) (fa[np] = 1, tail = np);
        int q = ch[p][c];
        if(dep[q] == dep[p] + 1) fa[np] = q;
        else{
            int nq = newnode(dep[p] + 1);
            fa[nq] = fa[q], fa[np] = fa[q] = nq;
            if(ff == 1) sz[nq] = sz[q];
            for(int i = 0; i < 26; i++) ch[nq][i] = ch[q][i];
            for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;	
        }tail = np;
    }
	inline void addedge(){
		for(int i = 2; i <= size; i++) g[fa[i]].push_back(i);
	}
	inline void dfs(int u){
		for(int i = 0; i < g[u].size(); i++){
			dfs(g[u][i]), sz[u] += sz[g[u][i]];
			rt[u] = Seg.merge(rt[u], rt[g[u][i]], 1, n);	
		}
	}	
	inline ll calc(char *s, int l, int r){
		tail = 1;
		v.clear(); ll len = strlen(s), ans = 0, all = 0;
		for(int i = 0; i < len; i++) ins(s[i] - 'a', 1, 0, i + 1);
		for(int i = 0; i < v.size(); i++){
			int u = v[i];
			for(int p = u; p; p = fa[p]) {
				if(dd[p]) break;
				if(sz[p]){
					if(l == 1 && r == n) ans += dep[p] - dep[fa[p]];
					else{
						int mxlen = Seg.query(rt[p], 1, 1, n, r) - l + 1;
						if(mxlen > dep[fa[p]]) 
							ans += Min(mxlen, dep[p]) - dep[fa[p]];
					}
				}
				all += dep[p] - dep[fa[p]], dd[p] = 1;
			}
		}
		for(int i = 0; i < v.size(); i++){
			int u = v[i];
			for(int p = u; p; p = fa[p]){
				if(!dd[p]) break; dd[p] = 0;
			}
		}
		return all - ans;
	}	
}van;
int main(){
	scanf("%s", s); n = strlen(s), read(Q);
	for(int i = 0; i < n; i++) van.ins(s[i] - 'a', 0);
	van.addedge(), van.dfs(1);
	while(Q--){
		int l, r;
		scanf("%s", s), read(l), read(r);
		printf("%lld\n", van.calc(s));
	}
	return 0;
}

评测结果