1
\$\begingroup\$

I tried solving the following problem by following the suggested approach to solving the problem in the problem tutorial. However, the online judge still says my solution exceeds the time limit. Is there a way to optimize the program to perform faster?

The Problem:

You are given n strings s1,s2,…,sn of length at most 8.

For each string si, determine if there exist two strings sj and sk such that si=sj+sk. That is, si is the concatenation of sj and sk. Note that j can be equal to k.

Recall that the concatenation of strings s and t is s+t=s1s2…spt1t2…tq, where p and q are the lengths of strings s and t respectively. For example, concatenation of "code" and "forces" is "codeforces".

Input

The first line contains a single integer t which can be 1 to 104— the number of test cases.

The first line of each test case contains a single integer n which can be 1 to 105— the number of strings.

Then n lines follow, the i-th of which contains non-empty string si of length at most 8, consisting of lowercase English letters. Among the given n strings, there may be equal (duplicates).

The sum of n over all test cases doesn't exceed 105.

Output

For each test case, output a binary string of length n. The i-th bit should be 1 if there exist two strings sj and sk where si=sj+sk, and 0 otherwise. Note that j can be equal to k.

Example

INPUT:

3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code

OUTPUT:

10100
011
10100101

The Problem Tutorial (Hint):

Use some data structure that allows you to answer queries of the form: "does the string t appear in the array s1,…,sn?" For example, in C++ you can use a map<string, bool>, while in Python you can use a dictionary dict.

Afterwards, for each string s, brute force all strings x and y such that s=x+y. There are at most 7 such strings, because s has length at most 8. Then check if both x and y appear in the array using your data structure.

The time complexity is O(ℓnlogn) per test case, where is the maximum length of an input string.

My Solution

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

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

    for (int i = 0; i < tests; i++) { //one loop per each test case
        int NumOfStrings;
        cin >> NumOfStrings;

        unordered_map<string, bool> phrases;
        string words[100000];

        for (int j = 0; j < NumOfStrings; j++) { // adds all input strings for each test case into words and phrases
            string temp;
            cin >> temp;
            phrases.insert({ temp, false });
            words[j] = temp;
        }

        for (int k = 0; k < NumOfStrings; k++) { // loop for each string in the test case
            int len = words[k].length(); // len is length of current word
            for (int o = 0; o < len; o++) { // loops through current word
                string partition1 = "";
                string partition2 = "";
                for (int m = 0; m <= o; m++) {
                    partition1 += words[k][m];
                }
                for (int n = o+1; n < len; n++) {
                    partition2 += words[k][n];
                }
                if (phrases.find(partition1) != phrases.end() && phrases.find(partition2) != phrases.end()) { //if both substrings exist in the map, then value for word is 1.
                    phrases[words[k]] = true;
                }
            }
        }
        for (int j = 0; j < NumOfStrings; j++) {
            int value = 0;
            if (phrases[words[j]] == true) value = 1;
            cout << value;
        }
        cout << endl;
    }
    return 0;
}

```
\$\endgroup\$
5
  • 5
    \$\begingroup\$ I think code review site might be better place to ask this question. \$\endgroup\$
    – Jiří
    Aug 14 at 15:37
  • 1
    \$\begingroup\$ It's not really on topic for this site. You might have more luck on codereview or stackoverflow. \$\endgroup\$
    – graffe
    Aug 14 at 16:03
  • 1
    \$\begingroup\$ I think Code Review would indeed be better for this, assuming your code works correctly and just hits the tester's time limit, and you're open to receive feedback about other aspects of the code like readability. See their tag info for time limit exceeded. I encourage you first though to look at the the program's actual runtime on tests of various sizes on your machine, and to use a profiler to understand the time breakdown and bottlenecks, and include these as question context. \$\endgroup\$
    – xnor
    Aug 14 at 18:50
  • 3
    \$\begingroup\$ IMO this would be perfectly on-topic as a fastest-code tips question. You've given a good specification of the problem, the code you have already, and an objective criterion to optimize. \$\endgroup\$ Aug 14 at 19:12
  • 2
    \$\begingroup\$ And it all ends happily....codereview.stackexchange.com/questions/278845/… \$\endgroup\$
    – graffe
    Aug 15 at 5:33

0

Browse other questions tagged or ask your own question.