Cerinta completa

Square Subsequences

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, “abab”, “aa” are square strings, while “aaa”, “abba” are not. Given a string, how many (non-empty) subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters.

Input Format

The first line contains the number of test cases, .
test cases follow. Each case contains a string, .

Output Format

Output lines, one for each test case, containing the required answer modulo 1000000007.

Constraints:

will have at most lowercase characters (‘a’ – ‘z’).

Sample Input

3
aaa
abab
baaba

Sample Output

3
3
6

Explanation

For the first case, there are 3 subsequences of length 2, all of which are square strings.
For the second case, the subsequences “abab”, “aa”, “bb” are square strings.
Similarly, for the third case, “bb”, “baba” (twice), and “aa” (3 of them) are the square subsequences.

Limbajul de programare folosit: cpp

Cod:

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

static inline long long getone(const char* s, int ns, const char* t, int nt, int last) {
    if (ns <= 0 || nt <= 0) return 1; // empty string only
    static long long dp[205][205];

    for (int i = 0; i < ns; ++i) {
        for (int j = last; j < nt; ++j) {
            long long a = (j >= 1 ? dp[i][j - 1] : 1);
            long long b = (i >= 1 ? dp[i - 1][j] : 1);
            long long c = (i >= 1 && j >= 1 ? dp[i - 1][j - 1] : 1);
            long long now = a + b - c;
            if (s[i] == t[j]) now += c;
            now %= MOD;
            if (now < 0) now += MOD;
            dp[i][j] = now;
        }
    }
    return dp[ns - 1][nt - 1];
}

static long long solveOne(const string& str) {
    int n = (int)str.size();
    long long ret = 0;
    const char* s = str.c_str();

    for (int i = 0; i < n; ++i) {
        char c = s[i];
        int last = 0;
        for (int j = i + 1; j < n; ++j) {
            if (s[j] == c) {
                ret += getone(s, i, s + i + 1, j - i - 1, last);
                ret %= MOD;
                if (j - i - 1 > 0) last = j - i - 1;
            }
        }
    }

    ret %= MOD;
    if (ret < 0) ret += MOD;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << solveOne(s) << '\n';
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464641571

Link challenge: https://www.hackerrank.com/challenges/square-subsequences/problem

Square Subsequences