实力强大的小 A 被选为了 ION2018 的出题人，现在他需要解决题目的命名问题。
小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小 A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小 A 有 次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串，详细可见输入格式。
大概就是讲给定一个串s，每次询问给一个串t和l，r，需要回答s(l,r)的所有子串和t的所有子串中有多少个不一样。
显然我们是要找一样的然后拿子串总数减去一样的。
那如找相同的子串呢？
首先考虑如果l = 1， r = n，把串t放在s的sam上跑，如果有对应的转移就转移，否则就跳到partent上去找转移，跳到根都没有就匹配下一个位置。
把t的每个位置在s的后缀自动机上匹配的长度数组称为p。我们构建t的后缀自动机，记录一下后缀自动机上每个结点的任意一个endpos。
然后我们dp的时候每个节点能贡献的不同的子串就是max(0, len[i] - max(len[fa[i]], p[endpos[i]]);
那么问题考虑l，r任意的情况，如何保证t只在s(l,r)的后缀自动机上匹配呢？在sam的每个结点上维护endpos就好，这里又用了线段树合并，这里的线段树的合并需要新开结点，不能破坏子结点的线段树。
我们还是继续把t放到s的后缀自动机上匹配，记录匹配长度，如果有转移，且有endpos在（l+p[i-1],r)中，就可以匹配，否则考虑减少匹配长度，当减到len[fa[x]]的时候就跳到partent上继续匹配。
代码基本是抄的。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
namespace Seg{
const int N = 1000100 * 20;
int rt[N], ls[N], rs[N], tot, n;
void init(const int &x) {n = x;return ;}
void ins(int &x,const int &p, int l = 1, int r = n) {
if (!x) x = ++tot;
if (l == r) return ;
int mid = (l + r) >> 1;
if (p <= mid) ins(ls[x], p, l, mid);
else ins(rs[x], p, mid + 1, r);
}
int add(const int &x) {
int res = ++tot;
ins(tot, x);
return res;
}
int merge(const int &x,const int &y) {
if (!x || !y) return x | y;
int res = ++tot;
ls[res] = merge(ls[x], ls[y]);
rs[res] = merge(rs[x], rs[y]);
return res;
}
int query(int x, int L, int R, int l = 1, int r = n) {
if (!x || r < L || l > R) return 0;
if (L <= l && r <= R) return 1;
int mid = (l + r) >> 1;
return query(ls[x], L, R, l, mid) + query(rs[x], L, R, mid + 1, r);
}
}
template<int N>
struct SAM{
int ch[N<<1][26], len[N<<1], minr[N << 1], fa[N << 1], rt[N << 1], tot, last;
void init() {tot = last = 1; memset(ch[1], 0, sizeof(ch[1]));}
SAM() {init();}
void ins(const int &x, const int &pos = 0) {
int p = last, np = ++tot; last = tot;
len[np] = minr[np] = len[p] + 1;
if (pos) rt[np] = Seg::add(pos);
memset(ch[np], 0, sizeof(ch[np]));
for (;p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
if (!p) return void(fa[np] = 1);
int q = ch[p][x];
if (len[q] == len[p] + 1) return void(fa[np] = q);
int nq = ++tot;
memcpy(ch[nq], ch[q], sizeof(ch[q]));
len[nq] = len[p] + 1;
minr[nq] = minr[q];
fa[nq] = fa[q];
fa[q] = fa[np] = nq;
for (;p && ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
}
void query(int &p, int &l, const int &L, const int &R, const int &x) {
while(1) {
if (ch[p][x] && ::Seg::query(rt[ch[p][x]], L + l, R)) {
p = ch[p][x];
l++;
return;
}
if (!l) return;
if (--l == len[fa[p]]) p = fa[p];
}
}
long long calc(int *p){
long long ans = 0;
for (int i = 2; i <= tot; i++) {
ans += max(0, len[i] - max(len[fa[i]], p[minr[i]]));
}
return ans;
}
};
SAM<500050> sam1;
SAM<1000050> sam2;
const int N = 5e5 + 100;
char s[N], t[N<<1];
int p[N<<1], c[N<<1], a[N<<1];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
Seg::init(n);
for (int i = 1; i <= n; i++) {
sam1.ins(s[i] - 'a', i);
}
for (int i = 1; i <= sam1.tot; i++) c[sam1.len[i]]++;
for (int i = 1; i <= n; i++) c[i] += c[i-1];
for (int i = 1; i <= sam1.tot; i++) a[c[sam1.len[i]]--] = i;
for (int i = sam1.tot; i; i--) {
sam1.rt[sam1.fa[a[i]]] = Seg::merge(sam1.rt[sam1.fa[a[i]]], sam1.rt[a[i]]);
}
int q;
scanf("%d", &q);
while (q--) {
scanf("%s", t + 1);
int l, r;
scanf("%d %d", &l, &r);
int cur = 1;//represent the position on the SAM of string s
sam2.init();
for (int i = 1; t[i]; i++) {
p[i] = p[i-1];
sam1.query(cur, p[i], l, r, t[i] - 'a');
sam2.ins(t[i] - 'a');
}
printf("%lld\n", sam2.calc(p));
}
}