İkili Axtarış II istifadə edərək ən uzun ümumi prefiks

Problem bəyanat

“İkili Axtarış II istifadə edərək ən uzun ümumi prefiks” problemində N və N tam ədədi verdik strings. Verilmiş simlərin ən uzun yayılmış prefiksini çap edəcək bir proqram yazın. Ortaq bir prefiks yoxdursa, yazdırın "-1".

Giriş Formatı

Sətirlərin sayını ifadə edən tam bir N dəyəri olan ilk sətir.

Sonra bir simli olan N sətir.

Çıxış formatı

Verilən N simli ən uzun yayılmış prefiksimiz olan “ans” simli olan ilk və tək sətir. Əgər belə bir prefiks yoxdursa, onda -1 yazdırın.

Məhdudiyyətlər

• 1 <= | N | <= 10 ^ 3
• 1 <= | s [i] | <= 10 ^ 3 burada i 0-dan N-1-ə
• s [i] [j], 0-dan N-1-ə, j-dən 0-dan | s [i] | -ə qədər olan kiçik bir İngilis əlifbası olmalıdır.

misal

5
abcde 
abba 
abaa 
abbbbb 
ababab

ab

Explanation: Burada 1-ci və XNUMX-ci simlərin ümumi prefiksinin “ab” olduğunu görə bilərik. İndi ikili axtarışdan istifadə edərək bu prefiksi digər simlərlə yoxlayın. “Ab” olan son prefiksi alırıq.

Binary Search II istifadə edərək ən uzun yayılmış prefiks üçün alqoritm

1. Minimum uzunluğa sahib olan simli tapın (L olsun) və giriş massivindən aşağı = 0 və Yüksək = L-1 olduğu sətirlərdən birində ikili axtarış aparın.

2. Sol hissədəki bütün simvollar müvafiq indekslərdə varsa, çıxışı qarışdırmaq üçün simvolları əlavə edin və daha uzun prefiksi tapmaq üçün sağ hissədə axtarın.

3. Başqa bir şey, sol hissədəki simvollar müvafiq indekslərdə yoxdursa, sağ hissədə axtarışa ehtiyac yoxdur. Ancaq solda axtarışa davam edin (yəni indeksdən orta indeksə başlayın)

Həyata keçirilməsi

Binary Search II istifadə edərək ən uzun yayılmış prefiks üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 

int min_length(vector<string> v) 
{ 
    int n=v.size();
  int mval = INT_MAX; 

  for (int i=0; i<=n-1; i++) 
    if (v[i].length() < mval) 
      mval = v[i].length(); 
  return mval; 
} 

bool allContainsPrefix(vector<string> v, int n, string str, 
          int start, int end) 
{ 
  for (int i=0; i<=n-1; i++) 
    for (int j=start; j<=end; j++) 
      if (v[i][j] != str[j]) 
        return (false); 
  return (true); 
} 

string common_prefix(vector<string> v) 
{ 
    int n=v.size();
  int index = min_length(v); 
  string prefix; 
  int low = 0, high = index; 

  while (low <= high) 
  { 
    int mid = low + (high - low) / 2; 
    if(allContainsPrefix (v, n, v[0], low, mid)) 
    { 
      prefix = prefix + v[0].substr(low, mid-low+1); 
      low = mid + 1; 
    } 
    else 
    {
        high = mid - 1;
    }
  } 
  return prefix; 
} 

int main() 
{ 
    int n;
    cin>>n;
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        v.push_back(x);
    }
    string ans = common_prefix(v);
  if(ans.length()) 
  {
      cout<<ans<<endl;
  }
  else
  {
      cout<<-1<<endl; 
  }
  return (0); 
} 

Binary Search II istifadə edərək ən uzun yayılmış prefiks üçün Java proqramı

import java.util.Scanner;
import java.util.Vector;
class sum
{
    public static int findMinLength(Vector<String> v) 
    { 
        int n=v.size();
  int min = Integer.MAX_VALUE; 
  for (int i = 0; i <= (n - 1); i++) 
  { 
    if (v.get(i).length() < min) { 
      min = v.get(i).length(); 
    } 
  } 
  return min; 
    }
    public static boolean allContainsPrefix(Vector<String> v, int n, String str, int start, int end) 
  { 
    for (int i = 0; i <= (n - 1); i++) 
    { 
      String arr_i = v.get(i); 
      
      for (int j = start; j <= end; j++) 
        if (arr_i.charAt(j) != str.charAt(j)) 
          return false; 
    } 
    return true; 
  }
    public static String common_prefix(Vector<String> v)
    {
                int n=v.size();
                int index = findMinLength(v); 
    String prefix = "";
    int low = 0, high = index-1; 
    while(low <= high){ 
      int mid = low + (high - low)/2; 
      if(allContainsPrefix(v, n, v.get(0), low, mid)==true) 
      { 
        prefix = prefix + v.get(0).substring(low, mid + 1); 
        low = mid + 1; 
      } 
      else 
      { 
        high = mid - 1; 
      } 
    } 
    return prefix; 
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        Vector<String> v = new Vector<String>(n+1);
        for(int i=0;i<n;i++)
        {
            String x = sr.next();
            v.add(x);
        }
        String ans = common_prefix(v);
        if(ans.length()!=0)
        {
            System.out.println(ans);
        }
        else
        {
            System.out.println("-1");
        }
    }
}

5
abcde 
abcd 
abcdefgh 
abcqwer 
abcdhfdiefi

abc

O (m) hara m maksimum sətrin uzunluğudur. Bu boşluğu simlər arasında bir əməliyyat etdikdən sonra ümumi prefiksi saxlamaq üçün istifadə edirik.