Longest Common Prefix of string 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 &lt;= 10^5. The sum of lengths of strings &lt;= 10^5.


#include &lt;bits/stdc++.h&gt;

using namespace std;

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

int lcp(string a, string b){
    int sol = 0;
    for (int i = 0; i &lt; 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 &gt;&gt; t;

    for (int e = 0; e &lt; t; ++e){
        int n;
        cin &gt;&gt; n;

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

        int q;
        cin &gt;&gt; q;

        for (int i = 0; i &lt; q; ++i){
            int l, r;
            cin &gt;&gt; l &gt;&gt; r;
            --l; --r;

            int sol = 0;
            for (int i = l; i &lt; r; ++i){
                for (int j = i + 1; j &lt;= 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 &lt;&lt; sol &lt;&lt; '\n';
        }
    }
}
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 &lt;bits/stdc++.h&gt;?".

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.