Brief description:
给定一段 Text、以及 nn 个 Pattern。要求这个 Text 中合法的子串数目，使得对于第 ii 个 Pattern，恰好能够匹配 [l_ii, r_ii] 之间次。
（nn ≤ 10）
Analysis:
SAM-DP。
我们把涉及到的所有字符串（Text && Patterns），依次插入到 SAM。（相邻的字符串之间，用彼此不同的分隔符隔开，以保证各字符串之间在 SAM 中不会相互干扰）
dp[ii][u] 表示：结点 u 所表示的子串集合，对于第 ii 个字符串的匹配次数。
http://codeforces.com/contest/316/submission/4749994
namespace SAM{
const int SN = int(5e4) + 1, NN = 11, N = 2*NN*SN + 9, Z = 26;
int trans[N][Z+NN], fail[N], len[N], tail, tot; char str[SN];
inline int new_node(){
// RST(trans[tot);
tail = tot;
return tot++;
}
inline int new_node(int u){
CPY(trans[tot], trans[u]), fail[tot] = fail[u];
return tot++;
}
#define v trans[u][c]
#define f fail[u]
#define ff fail[uu]
inline int h(int u){
return len[u] - len[f];
}
void Ext(int c){
int u = tail, uu = new_node(); len[uu] = len[u] + 1;
while (u && !v) v = uu, u = f;
if (!u && !v) v = uu, ff = 0;
else{
if (len[v] == len[u] + 1) ff = v;
else{
int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
fail[_v] = ff = vv;
while (v == _v) v = vv, u = f;
}
}
}
int dp[NN][N], l[NN], r[NN]; bool vis[N];
int nn, ans;
#define c (*cur - 'a')
void Init(){
tot = 0, new_node();
gets(str); REP_S(cur, str) Ext(c); Ext(Z);
REP_1_C(ii, RD(nn)){
RS(str); RD(l[ii], r[ii]);
REP_S(cur, str) Ext(c); Ext(Z+ii);
}
}
#undef c
inline bool legal(int u){
if (!u || !dp[0][u]) return 0;
REP_1(ii, nn) if (dp[ii][u] < l[ii] || r[ii] < dp[ii][u]) return 0;
return 1;
}
void dfs(int u = 0){
if (vis[u]) return; vis[u] = 1;
REP(ii, nn+1) if (trans[u][Z+ii]) dp[ii][u] = 1;
REP(c, Z) if (v){
dfs(v); REP(ii, nn+1) dp[ii][u] += dp[ii][v];
}
if (legal(u)) ans += h(u);
}
} using namespace SAM;
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
Init(); dfs(); OT(ans);
}
