Adding input strings and finding occurrences of certain prefixes A user inputs data using a keyword add word and when he wants to find  words with particular prefix then he enters find keyword.

Example input:

4 
add hack
add hacker
find hac
find hak


Output:

2
0


Although the code is working fine but for bigger cases it takes too much time.Please help me in reducing its time complexity.

#include&lt;iostream&gt;
#include&lt;vector&gt;
#include&lt;cstring&gt;
#include&lt;algorithm&gt;
using namespace std;
int main()
{
vector&lt;string&gt; v;
vector&lt;string&gt;::iterator i;
//char  *a;
string a,b;
int n;
cin&gt;&gt;n;
while(n--)
{

    cin&gt;&gt;a&gt;&gt;b;
      //char *Split = strtok (a," ");
    //vector&lt;char*&gt; Split = a.split_cstr(" ");
    if(a=="add")
{
    v.push_back(b);sort(v.begin(),v.end());}
    else if(a=="find")
    {  int mycount=0;
         //mycount = std::count (v.begin(), v.end(),find(b));
        //strncmp(string1, string2, strlen(string2))
        //          cout&lt;&lt;mycount&lt;&lt;endl;
        std::string prefix(b);

        //std::set&lt;std::string&gt;::iterator i;
        for (i = v.begin(); i != v.end(); ++i)
        {
           if ((*i).compare(0, prefix.length(), prefix) == 0)
              mycount++;    
            else if((*i).compare(0, prefix.length(), prefix) == 1)
              break;
        }       
        cout&lt;&lt;mycount&lt;&lt;endl;         
    }

 }

}
Let us just assume for simplicity that the upper bound for word length is some constant, so we can do some string operations on words, like checking if string a is prefix of b in constant time (i.e. \$O(1)\$). We will have N queries in total.

Naive solution

if (a == "add")
{
    v.push_back(b);
}
else if (a == "find")
{
    ...
    for (string word : v)
        if (is_prefix(prefix, word))
            mycount++;
    ...
}


Let us calculate time complexity for the worst case.

add operation: \$O(1)\$*

find operation: O(N) (assuming there are already N words added, we need to check each of them if it starts with prefix)

In total: \$N * (O(1) + O(N)) = O(N^2)\$

Your solution

add operation: \$O(N log N)\$ (for sorting)

find operation: \$O(N)\$ (even though we stop the search after the last matching word, it does not help in worst case, in which we have to check all the words)

In total: \$O(N^2 log N)\$

Even though the complexity seems to get worse, you are on the right track!

Possible improvement

Let K be the largest possible number of words find operation could find.
We can modify the solution to iterate only through words that start with prefix (K words at most). Because the vector is kept sorted, with binary search, that has \$O(log N)\$ complexity, we can find the first matching word without iterating through all the words from the beginning. In C++ std::lower_bound can do that job for you.

find operation: \$O(log N) + O(K)\$

Now let us improve add operation. It turns out, if we just replace std::vector with std::set, that is always sorted and has pretty good insertion/deletion complexity. The complexity for find will not change but add will be faster.

add operation: \$O(log N)\$

In total: \$N * (O(log N) + O(K) + O(log N)) = O(N log N + N * K)\$

It would be an improvement if K was some small constant. But as I now see that we are not even asked to output those words but only number of words, from my experience I would say we should not assume that K is small. The solution is probably checked against worst-case scenario that should look like this:

add aaa1
add aaa2
add aaa3
... (continue N/2 times)
find aaa
find aaa
find aaa
... (continue N/2 times)


If each find iterates through all the words, we get \$O(N/2 * N/2) = O(N^2)\$. This is not good. That probably means that we cannot event iterate through all matching words during find operation.

Better solution

Use prefix tree. Again, assuming constant word length, inserts will be constant:

add operation: \$O(1)\$

We will be able to find a subtree for all matching words in constant time too. Now we need to count words that belong to that subtree. Iterating trough all the children would be too slow. We will modify our tree to make each node store number of children. That number will be equal to the number of words that start with the prefix. It is possible to modify add operation to keep that number updated without changing the complexity of add.

find operation: \$O(1)\$

In total: \$O(N)\$