Coders Packet

Longest Common Prefix String in C++

By Saravanan.V

In this tutorial, we are going to learn how to find the longest common prefix string amongst an array of strings in C++.

Longest Common Prefix String

In a given array of strings, we have to find the longest common prefix string. The longest common prefix for an array of strings is the common prefix amongst an array of the strings. For example, in the given array {"flower", "flow", "flight"}, the common longest prefix is "fl". If the array  {"dog","racecar","car"},then there is no prefix string.

Approach:

To find the prefix we have to first find the smallest string because the longest prefix string must be the minimum length string or part of the minimum length string. Declare a count variable and increase it when the character of the string matches with the minimum length string. When it does not match, return the prefix string.

Pseudocode:

1.Find the minimum length string using a loop.
2.Declare count variable.
3.Make a nested loop. Outer loop for the minimum length string and inner loop for the strings in vector.
4.If the character of the string in vector matches the character in the minimum length string, increase the count. 
5.Else come out of the nested loop and print the substring of minimum length string.

Functions used:

substr:
substr is a predefined function used for string handling. It takes two values first index and last index and returns a copy of the string object. Syntax: string.substr(first index,last index). 

Code in C++:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  std::string v[10]={"flower","flow","flight"};
  string min_str;
  int str_length=INT_MAX,i,j,c=0,flag=0;
  for(i=0;i<3;i++)//TO FIND THE MINIMUM LENGTH STRING
{ int length=v[i].size(); if(str_length>length) { str_length=length; min_str=v[i]; } } for(i=0;i<min_str.length();i++)//ITERATION IN MINIMUM STR CHARACTERS { for(j=0;j<3;j++)//ITERATION THROUGH THE VECTOR OF STRINGS { if(v[j][i]!=min_str[i])//V[J][I] MEANS VECTOR OF Jth STRING OF Ith CHARACTER { flag=1; break; } } if(flag==1) { break;//TO BREAK THE OUTER LOOP } c++; } cout<<"Longest commom prefix string is "<<min_str.substr(0,c); }

Output:

Longest common prefix string is fl

 

Download project

Reviews Report

Submitted by Saravanan.V (Saravanan)

Download packets of source code on Coders Packet