How do I find the common prefix in strings?

[jasonkk]

Hi guys!

My assignment asks to find the common prefixes from user input, for example, user input -- "tiger" "teacup" "time" output : user inputs 3 strings and Common prefix is "t"

I have no idea to start with this coding since this assignment doesn't allow me to use an array and class.

and.. here is my starting..!

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string words;
    string common;
    cout <<"Please input the strings: "<< endl;
    getline(cin,words);
    for (int i=0; i<words.length(); ++i)
        {
          

[Ganado]

You can access words[i] to get the i'th letter (strings are basically fancy arrays).

Does that give you at least an idea of where to start?

In a nutshell, get one word. You now only have one word, so every letter is "common".
Then, when you get the next word, only save the letters that are in common with the existing common string (i.e. the previous word).
When you get the word after that, you repeat this, only saving the letters that are in common with the (now possibly reduced) common string.

Thee's multiple ways to actually get the first word from words. You can use a combination of string.find and string.substr to extract words (or, you can convert the string into a stringstream, then extract out each word with the >> operator).

[George P]

How are you going to store your 3 strings the user types in?

[Ganado]

You don't need to store the all the strings, only the previous one to compare to.

However, as the OP's code currently stands, there's no way to say what the number of words is before you actually get the words from the user, so basically all the words are being stored in the words array, presumably delimited by whitespace. The trick would then be to get n'th word out of the string to compare it to the (n-1)'th word.

[jasonkk]

Thank you guys for replying it,

but I still don't get how to find the common letters between the strings.

should I do the nested for loop in order to extract the same letters in strings?

Please let me know any suggestions..!

And, also the program should read the inputted strings until 'STOP' is typed.

[George P]

the program should read the inputted strings until 'STOP' is typed.

So, it isn't just 3 strings that need to be compared.

Are you familiar with while or do/while loops? Using one or the other will let you enter strings repeatedly until the user types "STOP".

#include <iostream>
#include <string>

int main()
{
   std::string prev_input;

   while (true)
   {
      std::cout << "Enter the string: ";
      std::string input;

      std::getline(std::cin, input);

      if (input == "STOP") { break; }  // get out of the loop

      if (prev_input == "")
      {
         std::cout << "\tFirst entered string!!!\n";

         prev_input = input;

         continue; // bypass the string comparison by restarting the loop
      }

      std::cout << '\t' << input << '\n';

      // logic for comparing current input to previous input
   }

   std::cout << "Good-bye!\n";
}

[jasonkk]

Thank you @Furry Guy,

now I'm trying to figure out how to find the common prefixes in the strings,

while(getline(cin,s))
{
s=com;
int n = 0;
while (s[n] == com[n])
++n;
}

I tried my best and spent three hours on this but still can't figure out.. what is wrong with this one?

[mbozzi]

#include <iostream>
#include <algorithm>
#include <string>

int main()
{
  std::string prefix;
  std::cin >> prefix;

  if (prefix == "STOP") return 0;
  
  for (std::string next; std::cin >> next && next != "STOP"; ) 
    prefix.assign(prefix.begin(), 
      std::mismatch(prefix.begin(), prefix.end(), next.begin(), next.end()).first);

  std::cout << prefix;
}

[mbozzi]

See also:

#include <iostream>
#include <string>

int first_mismatched_char(std::string const& a, std::string const& b)
{
  int result = 0; 
  
  while (a[result] == b[result] && (result != a.size()) && (result != b.size())) 
    ++result;
    
  return result;
}

int main()
{
  std::string prefix;
  std::cin >> prefix;

  if (prefix == "STOP") return 0;
  
  for (std::string next; std::cin >> next && next != "STOP"; ) 
    prefix = prefix.substr(0, first_mismatched_char(prefix, next));   

  std::cout << prefix;
}

[jasonkk]

Thank you @mabozz!!

this looks so good and thank you for your help!!

but this assignment doesn't allow any #include other than <iostream> and <string> since its very beginners class..

Right now I'm stuck right here ; what should I put in the 'do-while' loop for extract the common prefix?
int main()
{
bool stop = false;
string s;
string com;
int longest=0;

int numberofstring = 0;
string longest_str;

cout <<" Please input string"<<endl;
do
{
getline(cin,s);
if(s.size()>longest). // *** here, I try to out put the longest string but it always output 'STOP'
{
longest_str = s;
}
com = s;
for(int i = 0; i<com.length(); ++i)
{

++numberofstring;
if (s == "STOP")
{
stop = true;
}
}

[dutch]

@mbozzi, you need to check that result is in range before using it to access the strings.

while (result < a.size() && result < b.size() && a[result] == b[result])

You can also make it a little more efficient by simply resizing the prefix string (it can only get smaller):

#include <iostream>
#include <string>

void adjust_prefix(const std::string& word, std::string& prefix) {
    size_t i = 0;
    while (i < word.size() && i < prefix.size() && word[i] == prefix[i])
        ++i;
    prefix.resize(i);
}

int main() {
    std::string prefix;
    std::cin >> prefix;
    for (std::string word; std::cin >> word; )
        adjust_prefix(word, prefix);
    std::cout << prefix << '\n';
}

[mbozzi]

Thanks @dutch!

We also need a test to ensure that the initial prefix is not "STOP".