String Similarity

QUESTION

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings \”abc\” and \”abd\” is 2, while the similarity of strings \”aaa\” and \”aaab\” is 3.\n\nCalculate the sum of similarities of a string S with each of it’s suffixes.\n\nInput Format\n\nThe first line contains the number of test cases T. Each of the next T lines contains a string each.\n\nConstraints\n\n1 <= T <= 10 \nThe length of each string is at most 100000 and contains only lower case characters.\n\nOutput Format\n\nOutput T lines containing the answer for the corresponding test case. \n\nSample Input\n\n2\nababaa \naa\nSample Output\n\n11 \n3\nExplanation\n\nFor the first case, the suffixes of the string are \”ababaa\”, \”babaa\”, \”abaa\”, \”baa\”, \”aa\” and \”a\”. The similarities of these strings with the string \”ababaa\” are 6,0,3,0,1, & 1 respectively. Thus, the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.\n\nFor the second case, the answer is 2 + 1 = 3.

ANSWER

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <sstream>
#include <map>
#include <set>
#include <numeric>
#include <memory.h>
#include <cstdio>
#include <assert.h>
#include <numeric>

using namespace std;

#define pb push_back
#define INF 1011111111
#define FOR(i,a,b) for (int _n(b), i(a); i < _n; i++)
#define rep(i,n) FOR(i,0,n)
#define ford(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define CL(a,v) memset((a),(v),sizeof(a))
#define mp make_pair
#define X first
#define Y second
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))

typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;

vector<ll> z_func(const string &s)
{
    int n = s.size();
    vector<ll> z(n,0);
    int l = 0,r = 0;

    FOR(i,1,n)
    {
        if(i <= r)
            z[i] = min(z[i-l], (ll)r-i+1);

        while(i+z[i] < n && s[i+z[i]] == s[z[i]]) z[i] ++;

        if(i+z[i]-1 > r)
            r = i+z[i]-1, l = i;
    }

    return z;
}

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        string s;
        cin >> s;

        vector<ll> z = z_func(s);

        cout << 1LL*s.size() + accumulate(all(z), 0LL) << endl;
    }

	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.