Divide and Conquer istifadə edərək ən uzun yayılmış prefiks

Problem bəyanat

“Divide and Conquer istifadə edərək ən uzun yayılmış prefiks” problemində n və n tam ədədi verdik strings. Ən uzun yayılmış prefiksi yazdıracaq bir proqram yazın. Ortaq bir şey yoxdursa prefiks sonra “-1” yazdırın.

Giriş Formatı

Birinci sətirdə bir n ədədi var.

Növbəti hər birində bir simli olan sətir.

Çıxış formatı

Verilmiş simlərin ən uzun yayılmış prefiksini əks etdirən bir simli çap edin. Əgər belə bir prefiks sətri tapılmasa, “-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

3
tutorial 
tutcup 
turnin

tu

Explanation: Burada “tu” hər sətirdə təqdim olunan prefiks olduğunu görə bilərik.

Divide and Conquer istifadə edərək ən uzun yayılmış prefiks üçün alqoritm

Bu alqoritmdə bölün və fəth etmə yanaşması müzakirə olunur. Əvvəlcə simli massivləri iki hissəyə ayırırıq. Sonra sol hissə üçün, sonra da sağ hissə üçün eyni şeyi edirik. Bütün simlərin uzunluğu 1-ə çatana qədər bunu edəcəyik. İndi bundan sonra sol və sağ simlərin ümumi prefiksini qaytararaq fəth etməyə başlayacağıq.

1. Uzunluq 1-ə çatana qədər iplər massivini iki hissəyə bölün

2. İndi sol və sağ simlərin ümumi prefiksini qaytararaq fəth etməyə başlayın

Həyata keçirilməsi

Divide and Conquer istifadə edərək ən uzun yayılmış prefiks üçün C ++ proqramı

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

string commonPrefixUtil(string str1, string str2) 
{ 
  string result; 
  int n1 = str1.length(), n2 = str2.length(); 
  for (int i=0,j=0;i<n1&&j<n2;i++,j++) 
  { 
    if(str1[i]!=str2[j]) 
    {
        break; 
    }
    result.push_back(str1[i]); 
  } 
  return result; 
} 

string commonPrefix(string s[], int x, int y) 
{ 
  if(x==y) 
  {
      return s[x]; 
  }
  if(y>x) 
  { 
    int mid=x+(y-x)/2; 
    string s1 = commonPrefix(s, x, mid); 
    string s2 = commonPrefix(s, mid+1, y); 
    return commonPrefixUtil(s1, s2); 
  } 
} 
int main() 
{ 
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++)
  {
      cin>>s[i];
  }
  string ans = commonPrefix(s,0,n-1); 
  if(ans.length()>0) 
  {
      cout<<ans<<endl;
  }
  else
  {
    cout<<-1<<endl; 
  }
  return (0); 
} 

Divide and Conquer istifadə edərək ən uzun yayılmış prefiks üçün Java proqramı

import java.util.Scanner;

class sum { 
    
  static String commonPrefixUtil(String str1, String str2) { 
    String result = ""; 
    int n1 = str1.length(), n2 = str2.length(); 
    for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) 
                { 
      if(str1.charAt(i)!=str2.charAt(j)) 
                        { 
        break; 
      } 
      result += str1.charAt(i); 
    } 
    return result; 
  } 
  static String commonPrefix(String s[], int x, int y) { 
    if(x==y) 
                { 
                    return s[x]; 
    } 
    if(y>x) 
                { 
      int mid = x + (y-x)/2; 
      String s1 = commonPrefix(s, x, mid); 
      String s2 = commonPrefix(s, mid + 1, y); 
      return commonPrefixUtil(s1,s2); 
    } 
    return null; 
  } 
  public static void main(String[] args) 
        {
            Scanner sr = new Scanner(System.in);
            int n = sr.nextInt();
            String s[] = new String[n];
            for(int i=0;i<n;i++)
            {
                s[i]= sr.next();
            }
      String ans = commonPrefix(s,0,n-1); 
      if(ans.length()!=0) 
            { 
                System.out.println(ans); 
            } 
            else 
            { 
                System.out.println("-1"); 
            } 
  } 
} 

3
car 
carrace 
caramazing

car

Divide and Conquer istifadə edərək ən uzun yayılmış prefiks üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * m) hara n simlərin sayıdır və m maksimum sətrin uzunluğudur. Burada hər bir xarakteri ziyarət edirik, buna görə zaman mürəkkəbliyi O (n * m) olur.

Kosmik Mürəkkəblik

O (m * logn) nəticələnən simli və ya ən uzun prefiks simli saxladığımız üçün O (m * logn) olan yer ayırırıq.