- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define endl "\n"
- #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define ALL(x) x.begin(),x.end()
- #define SORT(x) sort(ALL(x))
- #define FOR(a,b,c) for(int (a)= (b);(a)<(c);++(a))
- #define REP(a,b) FOR(a,0,b)
- #define mp make_pair
- #define pb push_back
- #define pll pair<ll,ll>
- #define pii pair<int,int>
- #define vl vector<ll>
- #define vi vector<int>
- #define f first
- #define s second
- int ttt = 1, case_ = 0;
- int n, m, k;
- template <class myType>
- void print_arr(myType &arr, ll L, string sep){ REP(i,L){
- cout << arr[i]; if (i < L-1) cout << sep;
- } cout << endl; return; }
- /*
- For each index of X, we need to know what the longest prefix of S1 starting at that point is, and the longest prefix of S2 starting at that point
- Suppose P[i] = K
- Then for each length L from 0 to K, we have Q[i+L] possibilities
- We need to intelligently calculate ANS[L] = the max associated Q value for each P value of L
- Then the final answer is SUM(ANS)
- For a given length L:
- Considering each index such that P(i) >= L, what's the max value of Q(i+L)?
- This is ANS[L]
- For every adjacent pair of indices (i,i+1), I need to know which length prefixes of S1 can end at i, and which length prefixes can start at i+1
- For each prefix of S1, S1[:i], I want to know f(i) = the longest suffix of S1[:i] which is also a prefix of S1
- I can use the prefix function to find this
- */
- vi prefix_function(string S) {
- int sz = S.length();
- vi pi(sz);
- for (int i = 1; i < sz; i++) {
- int j = pi[i-1];
- while (j > 0 && S[i] != S[j])
- j = pi[j-1];
- if (S[i] == S[j])
- j++;
- pi[i] = j;
- }
- return pi;
- }
- vi longest_prefix_end(string S, string X) {
- int sz1 = S.length();
- int sz2 = X.length();
- string T = S + "$" + X;
- vi P = prefix_function(T);
- vi ret;
- for(int i = sz1+1; i < P.size(); i++) ret.pb(P[i]);
- return ret;
- }
- vi z_function(string S) {
- int x = S.length();
- vi z(x);
- for (int i = 1, l = 0, r = 0; i < x; ++i) {
- if (i <= r)
- z[i] = min (r - i + 1, z[i - l]);
- while (i + z[i] < x && S[z[i]] == S[i + z[i]])
- ++z[i];
- if (i + z[i] - 1 > r)
- l = i, r = i + z[i] - 1;
- }
- return z;
- }
- vi longest_prefix_start(string S, string X) {
- int sz1 = S.length();
- int sz2 = X.length();
- string T = S + "$" + X;
- vi P = z_function(T);
- vi ret;
- for(int i = sz1+1; i < P.size(); i++) ret.pb(P[i]);
- return ret;
- }
- void solve() {
- string S1, S2, X;
- cin >> S1 >> S2 >> X;
- n = S1.length();
- m = S2.length();
- k = X.length();
- vi S1_pref = prefix_function(S1); // prefix function for S1 alone
- vi X_S1 = longest_prefix_end(S1,X); // prefix function for S1 on X
- vi X_S2 = longest_prefix_start(S2,X); // Z function for S2 on X
- vi ans(n+1,-1);
- ll ret = 0LL;
- for(int i = -1; i < k; i++) {
- // consider every possible boundary (including the start and end of the array) and update ans[L1] = max(ans[L1], L2)
- // L1 is the longest prefix leading into the boundary, L2 is the longest leading out of it
- if (0 <= i && i < k-1) ans[X_S1[i]] = max(ans[X_S1[i]],X_S2[i+1]);
- else if (i == k-1) ans[X_S1[i]] = max(ans[X_S1[i]],0); // end boundary
- else ans[0] = max(ans[0],X_S2[i+1]); // start boundary
- }
- for(int i = n; i >= 0; i--) {
- ret += (ll) ans[i]+1;
- if (i) ans[S1_pref[i-1]] = max(ans[S1_pref[i-1]], ans[i]); // update the answer for the next shortest prefix finishing at that index
- }
- cout << ret << endl;
- retur
- }
- int main() {
- quick;
- cin >> ttt;
- while (ttt--) solve();
- return 0;
- }