## Problem Statement

A tandem is a non-empty __string__ repeated three times, like AAA for a non-empty string A. A tandem is interesting if the characters who follow A's incident aren't the same; otherwise, it's boring. How many interesting and boring tandems does a string s have?

Also see, __kth largest element in an array____ __and __Euclid GCD Algorithm__

### Input

There is only one test case available.

A string s appears on the first line of the input.

### Output

The result should have only one line with two space-separated integers indicating the string's number of interesting and boring tandems.

### Constraints

- 1 ≤ |s| ≤ 200000
- s consists of lower case English alphabets a to z.

### Example

#### Input

`abaaabaaabaaabbbb`

#### Output

`5, 3`

## Solution Approach

### Method 1: Naive Approach

We count how many intriguing and uninteresting tandems there are per length of A. Let's pretend that |A| equals L. As a result, the tandem's length is 3L.

Consider the numbers 0, L, 2L, 3L, and so on. Three of these roles will be covered by a 3L tandem. So (i,j,k) = (i,i+L,i+2L).

- The length of the longest prefix of s[i...N-1], s[j...N-1], and s[k...N-1] is LCP(i,j,k).
- The length of the longest suffix of s[0...i], s[0...j], and s[0...k] is LCS(i,j,k).

Let V = min(LCS(i,j,k),L) + min(LCP(i,j,k),L) - 1. Then:

- If V < L implies there are no tandems.
- If V≥L and LCP(i,j,k)>L, there are 0 interesting tandems and V−L+1 boring tandems.
- If V≥L and LCP(i,j,k)≤L, then there are one interesting tandem and V−L boring tandems.

### Method 2: O(n^{2})

Let's count how many tandems there are based on A's length. Assuming A=L, the tandem AAA is 3L long. For the time being, let's correct this L and then count all boring and fascinating 3L tandems. Our solution should be fast enough to allow us to execute this for each L[1, N/3].

Consider the letters s_{0}, s_{L}, s_{2L}, s_{3L}, etc.

There are about N/L positions like this. However, because L characters separate these, any tandem of length 3L covers exactly three of them. As a result, let's fix three nearby characters, say s_{i}, s_{j}, s_{k}, where (i,j) and (j,k) are separated by L characters, and then count all boring and interesting tandems that span these three.

The tandem must begin at some point in [iL+1, i]. Otherwise, it will not be able to cover s_{i} if it starts at some point i, and it will not be able to cover s_{k} if it starts at some location i_{L}. But it can't simply begin at any point! If we want the string s_{a,a+3L-1} to be tandem, we must ensure that the following conditions are met (by definition):

*s _{a}*

_{,}

_{a}_{+}

_{L}_{−1 }=

*s*

_{a}_{+}

_{L}_{,}

_{a}_{+2}

_{L}_{−1}=

*s*

_{a}_{+2}

_{L}_{,}

_{a}_{+3}

_{L}_{−1}

However, because of how we choose to position a, we get a≤i≤a+L-1, a+L≤j≤a+2L-1, and a+2L≤k≤a+3L-1. It indicates that the equality above can be broken down into two parts:

*s _{a}*

_{, }

_{i}_{ }=

*s*

_{a}_{+}

_{L}_{,}

*=*

_{j}*s*

_{a}_{+2}

_{L}_{,}

_{k}*s _{i}*

_{,}

_{a}_{+}

_{L}_{−1 }=

*s*

_{j}_{,}

_{a}_{+2}

_{L}_{−1}=

*s*

_{k}_{,}

_{a}_{+3}

_{L}_{−1}

These two equalities can be stated in a different ways. The first is identical to:

A common suffix of length i-a+1 must be shared by the strings s_{0,i},s_{0,j}, and s_{0,k}.

The second is the same as the first:

A common prefix of length a+L-i must exist between the strings s_{i, N-1}, s_{j, N-1}, and s_{k, N-1}.

This allows us to calculate the number of tandems that cover s_{i} s_{j}, and s_{k}. First, let's define two terms:

- The length of the longest prefix of s
_{i, N-1}, s_{j, N-1}, and s_{k, N-1}is LCP(i,j,k). - The length of the longest suffix of s
_{0,i},s_{0,j}, and s_{0,k}is LCS(i,j,k).

Min(LCS(i,j,k),L) and min(LCP(i,j,k),L) each take O(L) time to compute. The running time is O(N/L.L)=O(N) per L since we will do this about N/L times for each length L. As a result, the running time for each L[1, N/3] is O(N^{2}).

### Method 3: Hashing + Binary Search

Compare any two substrings in O(1) time. We can use binary search to speed up the computation of LCP and LCS. Hashing is one approach to performing quick substring comparisons.

Polynomial hashing will be used specifically. A base B and a modulus M are set. Now we'll define H, the hash function (S). For the string s = s_{0}s_{1}s_{2}.

H(s)=(v(s_{0})+v(s_{1})B^{1}+v(s_{2})B^{2}+v(s_{3})B^{3}+…+v(s_{N−1})B^{N−1}) mod M

where, v(c) is a character-to-number __mapping__ function.

This hash will be used to compare __substrings__ in O(1):

- Preprocess the text so that H(s) for every substring s can be computed in O(1) time.
- Compare their hashes, H(t) and H(s), to compare two substrings, s and t.

When two strings are equal, their hashes must also be identical. Unfortunately, even if they are not equal, the hashes may be identical. As a result, this hashing algorithm occasionally fails. However, wisely choosing B, M, and v(c) will most likely be accepted.

So, how do we prepare the string for use? The following are the main advantages of using polynomial hashing:

**Concatenation**: Given H(s), H(t) and H(st) can be computed in O(1) time as H(st) = (H(s) + H(t)B^{|s|})mod M.**Splitting**: Given H(st), H(t) and H(s) can be computed in O(1) time as H(s) = (H(st) - H(t)B^{|s|})mod M.

These are the attributes that can be used to preprocess. We compute the hashes of all the string's prefixes. Using the concatenation property may be done in O(N) time. Then, to compute the hash, identify the necessary suffixes st and t, then use the splitting property to compute H(s) from H(st) and H(t)!

#### C++ implementation

```
/* C++ implementation */
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
/* Variables */
const int N = 2e3+5;
const int M = 1e2+2;
const int mod = 1e9+7;
const ll base = 751;
const int inf = 1e9;
/* Calling variables */
int m, n, t, d[N], lab[N];
int k, a[N], sum[N];
ll ans, tong, b[N];
vector<int> adj[N];
vector<pii> vi;
string s;
bool vis[N];
ll pw(ll k, ll n)
{
ll total = 1;
for(; n; n >>= 1)
{
if(n&1)total = total * k % mod;
k = k * k % mod;
}
return total;
}
/* Creating addition function with upper limit */
void add(int &x, int y)
{
x += y;
if(x >= mod)x -= mod;
}
/* Implementing hashing creating struct */
struct Hash
{
int n;
const ll mod = 1e9+7;
const int base = 521;
string s;
vector<ll> a, p;
/* Main class inside struct */
Hash(string _s)
{
s = _s;
n = s.length();
a.resize(n+1);
p.resize(n+1);
a[0] = 0;
p[0] = 1;
for(int i = 1; i <= n; i ++)
{
a[i] = (1ll*a[i-1] * base % mod + b[s[i-1]-'a']) % mod;
p[i] = 1ll*p[i-1]*base%mod;
}
}
/* Returning function inside struct */
int get(int l, int r)
{
return 1ll*(a[r]-a[l-1]*p[r-l+1]%mod+mod)%mod;
}
/* Retrieving LCP value */
int lcp(int u, int v)
{
int l = 1, r = min(v, n-u-v*2+1), mid;
while(l <= r)
{
mid = (l+r)>>1;
t = get(u, u+mid-1);
if(t == get(u+v, u+v+mid-1) && t == get(u+v*2, u+v*2+mid-1))l = mid+1;
else r = mid-1;
}
return r;
}
/* Retrieving LCS value */
int lcs(int u, int v)
{
int l = 1, r = min(v, u), mid;
while(l <= r)
{
mid = (l+r)>>1;
t = get(u-mid+1, u);
if(t == get(u+v-mid+1, u+v) && t == get(u+v*2-mid+1, u+v*2))l = mid+1;
else r = mid-1;
}
return r;
}
};
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
/* Main algo function */
void sol()
{
cin >> s;
for(int j = 0; j < 26; j ++)b[j] = mt() % mod;
n = s.length();
Hash pre(s);
ll res1 = 0, res2 = 0;
int l, r;
for(int i = 1; i*3 <= n; i ++)
{
for(int j = 1; j <= n-i*2+1; j += i)
{
l = pre.lcp(j, i);
r = pre.lcs(j, i);
k = l+r-i;
if(k <= 0)continue;
/* cout << j <<" "<<i<<" "<<l<<'\n'; */
l = j-(i-l);
if(l+i*3 > n || s[l-1] != s[l+i*3-1])
{
res1 += 1;
res2 += k-1;
}
else res2 += k;
}
}
cout << res1 <<" "<<res2;
}
/* Main Code */
int main()
{
/* Getting value */
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
/* Running sol function and showing values */
while(test -- > 0)sol();
return 0;
}
```

Input

`abaaabaaabaaabbbb`

Output

`5, 3`

**Complexities**

**Time complexity****O(N log ^{2}N)**

**Reason:**LCP and LCS are computed with

__binary search__, which takes O(log N) time each, so doing that N/L times gives O(N/LlogN), which on calculation gives O(N log

^{2}N).

**Space complexity****O(N)****Reason: **Implementing binary search and to display we need a vector of size N.

Check out this problem - __Maximum Product Subarray__