Longest Common Prefix of string

Question

Can anyone help me remove TLE (time limit exceeded) from this?

Given integer n and array of string of length n. In each query (q of them) we are given l and r and we need to find LCP in this subsequence. Q and N <= 10^5. The sum of lengths of strings <= 10^5.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

int lcp(string a, string b){
    int sol = 0;
    for (int i = 0; i < min(b.size(), a.size()); ++i){
        if (a[i] == b[i])
            ++sol;
        else
            break;
    }

    return sol;
}

int d[10000][10000];

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);  

    int t;
    cin >> t;

    for (int e = 0; e < t; ++e){
        int n;
        cin >> n;

        vs s(n);
        for (auto& i : s)
            cin >> i;

        int q;
        cin >> q;

        for (int i = 0; i < q; ++i){
            int l, r;
            cin >> l >> r;
            --l; --r;

            int sol = 0;
            for (int i = l; i < r; ++i){
                for (int j = i + 1; j <= r; ++j){
                    if (!d[i][j]){
                        d[i][j] = lcp(s[i], s[j]);
                        if (d[i][j] == 0)
                            d[i][j] = -1;
                    }
                    sol = max(sol, d[i][j]);
                }
            }

            cout << sol << '\n';
        }
    }
}

Could you clarify what is being required of this code as a point of correctness, before looking at performance? From the description, it sounds like you want a prefix: that is, a string which consists of the first n characters of another string. Whereas your function returns the length of the prefix. — Josiah
– Josiah, Commented Apr 19, 2018 at 21:22

Deduplicator · Accepted Answer · 2018-04-19 20:56:37Z

First of all, absurd terseness does not imply lightning speed. Quite the contrary, it makes understanding and thus optimizing that much more difficult.

So, get some useful names.

Anyway, if you want to go for reasonable brevity, or just remove some confusion, remove all the unused typedefs. And then remove the rest of them too, as they also have negative value.

Now, a tip for getting a stunning performance-boost:
Stop copying things, especially if doing so needs dynamic allocation.
That means lcp() should receive its arguments by constant reference.

Next, hopefully your compiler hoists min(b.size(), a.size()) out of the loop. Still, do you really want to rely on that?

Are you sure you need all the headers, and want to live with the unportability?
Read "Why should I not #include <bits/stdc++.h>?".

And also, don't pollute the global namespace with all kinds of things, which you are unlikely to know for now, let alone the future.
See Why is “using namespace std” considered bad practice? for more elaboration on that.

It is common to do this kind of code in a contest where you need to solve and code as fast as possible. If it not real time though, better to have something understandable as you propose — juvian
– juvian, Commented Apr 19, 2018 at 21:03

Stack Exchange Network

Longest Common Prefix of string

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Longest Common Prefix of string

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions