rxYwpv - Online C++0x Compiler & Debugging Tool

// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 2e5 + 5;
int lenStr, numStr, ans[N], cntSame[N];
string pattern;
string str[N];
vector<int> startPos[N], endPos[N];
map<string, int> id;
int cntStart[N];
bool haveStart[N];

struct Aho_Corasick {
    const static int MAX_NODE = 26;
    const static char LOWER = 'a';
    struct Node {
        Node *link, *child[MAX_NODE], *go[MAX_NODE], *nearAsk;
        int id;
        vector<Node*> G;
        Node() {
            link = nearAsk = NULL;
            REP(i, MAX_NODE) child[i] = go[i] = NULL;
            id = 0;
        }
    };

    Node *root;
    Aho_Corasick() {
        root = new Node();
    }

    void add(string &s, int id) {
        Node *p = root;
        for(char c : s) {
            int pos = c - LOWER;
            if (p -> child[pos] == NULL) {
                p -> child[pos] = new Node();
                p -> go[pos] = p -> child[pos];
            }
            p = p -> child[pos];
        }
        p -> id = id;
    }

    void BFS() {
        queue<Node*> q;
        REP(pos, MAX_NODE) {
            if (root -> child[pos] == NULL) {
                root -> child[pos] = new Node();
                root -> go[pos] = root -> child[pos];
            }
            q.push(root -> child[pos]);
            root -> G.pb(root -> child[pos]);
            root -> child[pos] -> link = root;
        }

        while(!q.empty()) {
            auto p = q.front(); q.pop();
            REP(pos, MAX_NODE) {
                if (p -> child[pos] == NULL) {
                    p -> go[pos] = p -> link -> go[pos];
                } else {
                    q.push(p -> child[pos]);
                    p -> child[pos] -> link = p -> link -> go[pos];
                    p -> link -> go[pos] -> G.pb(p -> child[pos]);
                }
            }
        }
    }

    void DFS(Node *u, Node *preAsk) {
        u -> nearAsk = preAsk;
        for(auto v : u -> G) {
            if (u -> id == 0) DFS(v, preAsk);
            else DFS(v, u);
        }
    }

    void queryPattern(string &s) {
        Node *p = root;
        REP(i, (int)s.size()) {
            int pos = s[i] - LOWER;
            p = p -> go[pos];
            auto tmp = p;

            if (tmp -> id == 0) tmp = tmp -> nearAsk;
            while(tmp != NULL) {
                endPos[tmp -> id].pb(i);
                tmp = tmp -> nearAsk;
            }
        }
    }
} aho;

ll countGlobal(int i) {
    ll ans = 0;
    for(int pos : startPos[i]) cntStart[pos] -= cntSame[i];
    for(int pos : endPos[i]) ans += 1LL * cntSame[i] * cntStart[pos + 1];
    for(int pos : startPos[i]) cntStart[pos] += cntSame[i];
    return ans;
}

ll countInternal(int i) {
    ll ans = 0;
    for(int pos : startPos[i]) haveStart[pos] = true;
    for(int pos : endPos[i]) if (haveStart[pos + 1])
        ans += 1LL * cntSame[i] * cntSame[i];
    for(int pos : startPos[i]) haveStart[pos] = false;
    return ans;
}

void init(void) {
    cin >> pattern;
    lenStr = (int)pattern.size();
    cin >> numStr;
    FOR(i, 1, numStr) {
        cin >> str[i];
        if (id[str[i]] == 0) id[str[i]] = i;
        cntSame[id[str[i]]]++;
    }
}

void process(void) {
    FOR(i, 1, numStr) if (id[str[i]] == i) {
        aho.add(str[i], i);
    }
    aho.BFS();
    aho.DFS(aho.root, NULL);
    aho.queryPattern(pattern);
    FOR(i, 1, numStr) if (id[str[i]] == i) {
        for(int pos : endPos[i]) {
            int start_pos = pos - (int)str[i].size() + 1;
            startPos[i].pb(start_pos);
            cntStart[start_pos] += cntSame[i];
        }
    }

    ll ans = 0;
    FOR(i, 1, numStr) if (id[str[i]] == i) {
        ans += countGlobal(i);
        ans += countInternal(i);
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}