1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ALL(x) x.begin(),x.end()
  7. #define SORT(x) sort(ALL(x))
  8. #define FOR(a,b,c) for(int (a)= (b);(a)<(c);++(a))
  9. #define REP(a,b) FOR(a,0,b)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define vl vector<ll>
  15. #define vi vector<int>
  16. #define f first
  17. #define s second
  18. int ttt = 1, case_ = 0;
  19. int n, m, k;
  20. template <class myType>
  21. void print_arr(myType &arr, ll L, string sep){ REP(i,L){
  22. cout << arr[i]; if (i < L-1) cout << sep;
  23. } cout << endl; return; }
  24. /*
  25. 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
  26. Suppose P[i] = K
  27. Then for each length L from 0 to K, we have Q[i+L] possibilities
  28. We need to intelligently calculate ANS[L] = the max associated Q value for each P value of L
  29. Then the final answer is SUM(ANS)
  30. For a given length L:
  31. Considering each index such that P(i) >= L, what's the max value of Q(i+L)?
  32. This is ANS[L]
  33. 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
  34. 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
  35. I can use the prefix function to find this
  36. */
  37. vi prefix_function(string S) {
  38. int sz = S.length();
  39. vi pi(sz);
  40. for (int i = 1; i < sz; i++) {
  41. int j = pi[i-1];
  42. while (j > 0 && S[i] != S[j])
  43. j = pi[j-1];
  44. if (S[i] == S[j])
  45. j++;
  46. pi[i] = j;
  47. }
  48. return pi;
  49. }
  50. vi longest_prefix_end(string S, string X) {
  51. int sz1 = S.length();
  52. int sz2 = X.length();
  53. string T = S + "$" + X;
  54. vi P = prefix_function(T);
  55. vi ret;
  56. for(int i = sz1+1; i < P.size(); i++) ret.pb(P[i]);
  57. return ret;
  58. }
  59. vi z_function(string S) {
  60. int x = S.length();
  61. vi z(x);
  62. for (int i = 1, l = 0, r = 0; i < x; ++i) {
  63. if (i <= r)
  64. z[i] = min (r - i + 1, z[i - l]);
  65. while (i + z[i] < x && S[z[i]] == S[i + z[i]])
  66. ++z[i];
  67. if (i + z[i] - 1 > r)
  68. l = i, r = i + z[i] - 1;
  69. }
  70. return z;
  71. }
  72. vi longest_prefix_start(string S, string X) {
  73. int sz1 = S.length();
  74. int sz2 = X.length();
  75. string T = S + "$" + X;
  76. vi P = z_function(T);
  77. vi ret;
  78. for(int i = sz1+1; i < P.size(); i++) ret.pb(P[i]);
  79. return ret;
  80. }
  81. void solve() {
  82. string S1, S2, X;
  83. cin >> S1 >> S2 >> X;
  84. n = S1.length();
  85. m = S2.length();
  86. k = X.length();
  87. vi S1_pref = prefix_function(S1); // prefix function for S1 alone
  88. vi X_S1 = longest_prefix_end(S1,X); // prefix function for S1 on X
  89. vi X_S2 = longest_prefix_start(S2,X); // Z function for S2 on X
  90. vi ans(n+1,-1);
  91. ll ret = 0LL;
  92. for(int i = -1; i < k; i++) {
  93. // consider every possible boundary (including the start and end of the array) and update ans[L1] = max(ans[L1], L2)
  94. // L1 is the longest prefix leading into the boundary, L2 is the longest leading out of it
  95. if (0 <= i && i < k-1) ans[X_S1[i]] = max(ans[X_S1[i]],X_S2[i+1]);
  96. else if (i == k-1) ans[X_S1[i]] = max(ans[X_S1[i]],0); // end boundary
  97. else ans[0] = max(ans[0],X_S2[i+1]); // start boundary
  98. }
  99. for(int i = n; i >= 0; i--) {
  100. ret += (ll) ans[i]+1;
  101. 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
  102. }
  103. cout << ret << endl;
  104. retur
  105. }
  106. int main() {
  107. quick;
  108. cin >> ttt;
  109. while (ttt--) solve();
  110. return 0;
  111. }
Comments powered by Disqus