#include <bits/stdc++.h>   using namespace std;   struct State {     int len, link;     map<char, int> nxtc;   } SA[2 * 2006];   bool vis[2 * 2006];   char str[2006], pref[2 * 2006], suf[2006];   class SuffixAutomata {     int sz, last;     void init(int idx) {       SA[idx].len = 0, SA[idx].link = -1;       SA[idx].nxtc.clear();     }     bool traverse(int cur, char *ch) {       if (*ch == 0) return true;       if (SA[cur].nxtc.count(*ch) == 0) return false;       int p = SA[cur].nxtc[*ch];       return traverse(p, ++ch);     }     int findState(int cur, char *ch) {       if (*ch == 0) return cur;       int p = SA[cur].nxtc[*ch];       return findState(p, ++ch);     }       public:     SuffixAutomata() {       sz = last = 0;       init(0);       ++sz;     }     int size() { return sz; }     void extend(char ch) {       int p, q, clone, cur = sz++;       init(cur);       SA[cur].len = SA[last].len + 1;       for (p = last; p != -1 && SA[p].nxtc.count(ch) == 0; p = SA[p].link)         SA[p].nxtc[ch] = cur;       if (p == -1)         SA[cur].link = 0;       else {         q = SA[p].nxtc[ch];         if (SA[p].len + 1 == SA[q].len)           SA[cur].link = q;         else {           clone = sz++;           init(clone);           SA[clone] = SA[q];           SA[clone].len = SA[p].len + 1;           for (; p != -1 && SA[p].nxtc[ch] == q; p = SA[p].link)             SA[p].nxtc[ch] = clone;           SA[cur].link = SA[q].link = clone;         }       }       last = cur;     }     bool traverse(char *str) { return traverse(0, str); }     int findState(char *str) { return findState(0, str); }   };   int lenp, lens, dp[2 * 2006][2006];   int rec(int cur, int idx) {     if (suf[idx] == 0) return 1;     if (dp[cur][idx] != -1) return dp[cur][idx];     int &ret = dp[cur][idx];     ret = 0;     char ch;     int p;     if (idx) {       ch = suf[idx];       if (SA[cur].nxtc.count(ch) == 0) return ret = 0;       p = SA[cur].nxtc[ch];       return ret = rec(p, idx + 1);     }     map<char, int> &M = SA[cur].nxtc;     map<char, int>::iterator im;     for (im = M.begin(); im != M.end(); ++im) {       ch = im->first;       p = im->second;       ret += rec(p, idx);       if (ch == suf[idx]) ret += rec(p, idx + 1);     }     return ret;   }   int main() {     int i, j, ans, n;     while (scanf( %s , str) != EOF) {       SuffixAutomata sa;       for (i = 0; str[i]; ++i) sa.extend(str[i]);       ans = 0;       scanf( %s %s , pref, suf);       lenp = strlen(pref), lens = strlen(suf);       if (!sa.traverse(pref)) {         puts( 0 );         continue;       }       for (i = 0; i < lenp; ++i) {         if (i + lens < lenp) continue;         for (j = 0; j < lens; ++j) {           if (pref[i + j] != suf[j]) break;         }         if (i + j == lenp) {           strcat(pref, &suf[lenp - i]);           ans += sa.traverse(pref);           pref[lenp] = 0;         }       }       n = sa.findState(pref);       memset(dp, -1, sizeof(dp));       ans += rec(n, 0);       printf( %d n , ans);     }     return 0;   }   