# ABBYY Cup 3.0 G3. Good Substrings

（nn ≤ 10）

### Analysis:

SAM-DP。

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;
}
inline int new_node(int u){
CPY(trans[tot], trans[u]), fail[tot] = fail[u];
}

#define v trans[u]
#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);
}