最長公共前綴

Problem statement:

問題陳述：

Write a function to find the longest common prefix string amongst an array of strings.

編寫函數以在字符串數組中找到最長的公共前綴字符串 。

If there is no common prefix, return an empty string "".

如果沒有公共前綴，則返回一個空字符串“” 。

Solution:

解：

Input Example:

輸入示例：

    Example 1:
Let the set of strings to be {"flower", "fly", "flow"}
The longest common prefix is "fl"
Example 2:
Let the set of strings to be {"dog", "donkey", "door", "cat"}
The longest common prefix is "", i.e., empty string. 
Since there is no common prefix at all. 

最長的公共前綴 (Longest common prefix)

Longest common prefix simply means the longest prefix (prefix is a substring also, but not vice-versa) all the member strings consist of.

最長公共前綴僅表示所有成員字符串組成的最長前綴(前綴也是子字符串，反之亦然)。

查找一組字符串的最長公共前綴的算法 (Algorithm to find longest common prefix of a set of strings)

Solving particularly for two string, the problem is not that difficult what it is for a set of strings. But we can simply break the problem into sub-problems where we can solve for only two strings and simply pass the output for further string processing 's. In a simple word, the whole thing can be formulated to be:

特別是對于兩個字符串，解決的問題并不像一組字符串那么困難。 但是我們可以簡單地將問題分解為幾個子問題，在這些子問題中，我們只可以解決兩個字符串，然后將輸出傳遞給進一步的字符串處理。 簡而言之，整個事情可以表述為：

    LongestCommonPrefix(string1, string2, ..., string n)
=   LongestCommonPrefix(LongestCommonPrefix(string1,string2),string3,...,string n)
=   LongestCommonPrefix(newstring1,string3,string4,...,string n)
=   ...
=   LongestCommonPrefix(newstring n-1, string n)
=   new string n = final result

So this simply converts the problem for a set of 
strings to a problem of two strings only

Finding longest common prefix for two strings (string x, string y)

查找兩個字符串(字符串x，字符串y)的最長公共前綴

1. Check for base case

   檢查基本情況

2. IF anyone is empty string
   return empty string;
   
   

3. Declare result as an empty string;

   將結果聲明為空字符串；

4.     IF string x is smaller than y
   //check for common prefix part on basis of x
   FOR( i=0;i<length of string x; i++)
   IF(x[i]==y[i])
   result+=x[i]; //append the common character
   ELSE//no common character at this point
   Returnresult
   END FOR
   ELSE//if string y is smaller than x
   //check for common prefix part on basis of y		
   FOR (i=0;i<length of y; i++)
   IF(y[i]==x[i])
   result+=y[i];//append the common character
   ELSE//no common character at this point
   return result;
   END FOR
   END IF-ELSE
   
   

5. result consist of longest common prefix for these two strings

   結果由這兩個字符串的最長公共前綴組成

Explanation with example

舉例說明

    Let's consider the first example
The set of strings: {"flower", "fly", "flow"}
LongestCommonPrefix("flower", "fly", "flow")
=   LongestCommonPrefix(LongestCommonPrefix ("flower","fly"),"flow")
=   LongestCommonPrefix("fl", "flow")
=   "fl"
Let's consider the second example
the set of strings to be {"dog", "donkey", "door", "cat"}
LongestCommonPrefix("dog", "donkey", "door", "cat")
=   LongestCommonPrefix(LongestCommonPrefix ("dog", "donkey"),"door", "cat")
=   LongestCommonPrefix("do","door", "cat")
=   LongestCommonPrefix (LongestCommonPrefix("do", "door") , "cat")
=   LongestCommonPrefix("do", "cat")
=   "" //empty string

C++ implementation

C ++實現

#include <bits/stdc++.h>
using namespace std;
string findPrefix(string x,string y){
//base case checking
if(x=="" || y=="")
return "";
string result="";
//if string x is smaller than y
if(x.length()<y.length()){
//check up for common prefix part
for(int i=0;i<x.length();i++){
if(x[i]==y[i])
result+=x[i];
}
}
else{
//if string y is smaller than x
for(int i=0;i<y.length();i++){
//check up for common prefix part 
if(y[i]==x[i])
result+=y[i];
else
return result;
}
}
return result;
}
string longestCommonPrefix(vector<string>& strs) {
//base cases
if(strs.size()==0)
return "";
//if only one string exists
if(strs.size()==1)
return strs[0];
string prefix=strs[0];
//follow the associative property for checking 
//take two strings each time & pass output prefix 
//as one string for further processings
for(int i=1;i<strs.size();i++){
prefix=findPrefix(prefix,strs[i]);
if(prefix=="")
return prefix;
}
return prefix;
}
int main(){
int n;
cout<<"enter no of strings you want to add\n";
cin>>n;
string s;
vector<string> v;
cout<<"enter "<<n<<" strings\n";
//collect input
while(n--){
cin>>s;
v.push_back(s);
}
//print longest common prefix
if(longestCommonPrefix(v)=="")
cout<<"no common prefix between the strings\n";
else
cout<<"longest common prefix: "<<longestCommonPrefix(v)<<endl;
return 0;
}

Output

輸出量

First run:
enter no of strings you want to add
3
enter 3 strings
flower
fly
flow
longest common prefix: fl
Second run:
enter no of strings you want to add
4
enter 4 strings
dog
donkey
door
cat
no common prefix between the strings

翻譯自: https://www.includehelp.com/icp/longest-common-prefix.aspx

最長公共前綴