බෙදීම සහ යටත් කර ගැනීම භාවිතා කරන දීර් est තම පොදු උපසර්ගය  


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇසොලයිට් ඇමේසන් උන්මත්තකයෝ ගූගල්
බෙදන්න සහ ජය ගන්න String

ගැටළු ප්රකාශය  

“බෙදීම සහ යටත් කර ගැනීම භාවිතා කරන දීර් est තම පොදු උපසර්ගය” ගැටලුවේදී, අපි පූර්ණ සංඛ්‍යා n සහ n ලබා දී ඇත නූල්. දීර් est තම පොදු උපසර්ගය මුද්‍රණය කරන වැඩසටහනක් ලියන්න. පොදු නොවේ නම් උපසර්ගය ඉන්පසු “-1” මුද්‍රණය කරන්න.

ආදාන ආකෘතිය  

පළමු පේළියේ පූර්ණ සංඛ්‍යාවක් n අඩංගු වේ.

එක් පේළියක් අඩංගු ඊළඟ පේළිය.

නිමැවුම් ආකෘතිය  

දී ඇති නූල් වල දීර් est තම පොදු උපසර්ගය නියෝජනය කරන නූලක් මුද්‍රණය කරන්න. එවැනි උපසර්ගයක් සොයාගත නොහැකි නම් “-1” මුද්‍රණය කරන්න.

අවහිරතා  

  • 1 <= n <= 10 ^ 3
  • 1 <= | s [i] | <= 10 ^ 3 එහිදී මම 0 සිට n-1 දක්වා
  • s [i] [j] යනු 0 සිට n-1 දක්වා සහ j 0 සිට | s [i] |

උදාහරණයක්  

3
tutorial 
tutcup 
turnin
tu

පැහැදිලි කිරීම: මෙහිදී අපට දැක ගත හැකි වන්නේ “tu” යනු සෑම නූලකම ඉදිරිපත් කරන උපසර්ගයයි.

බෙදීම සහ ජය ගැනීම භාවිතා කරමින් දීර් est තම පොදු උපසර්ගය සඳහා ඇල්ගොරිතම  

මෙම ඇල්ගොරිතමයේදී, බෙදීම් සහ ජය ගැනීමේ ප්‍රවේශයක් සාකච්ඡා කෙරේ. අපි මුලින්ම නූල් අරා කොටස් දෙකකට බෙදමු. එවිට අපි වම් කොටස සඳහාත් පසුව දකුණු කොටස සඳහාත් එසේ කරමු. සියලුම නූල් දිග 1 වන තෙක් සහ නැතිනම් අපි එය කරන්නෙමු. දැන් ඊට පසු, වම් සහ දකුණු නූල්වල පොදු උපසර්ගය නැවත ලබා දීමෙන් අපි ජය ගැනීමට පටන් ගනිමු.

මෙයද බලන්න
කුඩාම හොඳ පදනම

1. දිග 1 වන තෙක් නූල් පෙළ කොටස් දෙකකට පුනරාවර්තනය කරන්න

2. දැන්, වම් සහ දකුණු නූල්වල පොදු උපසර්ගය නැවත ලබා ගැනීමෙන් ජය ගැනීම ආරම්භ කරන්න

ක්රියාත්මක කිරීම  

බෙදීම සහ ජය ගැනීම භාවිතා කරමින් දීර් est තම පොදු උපසර්ගය සඳහා C ++ වැඩසටහන

#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); 
} 

බෙදීම සහ ජය ගැනීම භාවිතා කරමින් දීර් est තම පොදු උපසර්ගය සඳහා ජාවා වැඩසටහන

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

බෙදීම සහ ජය ගැනීම භාවිතා කරමින් දීර් est තම පොදු උපසර්ගය සඳහා සංකීර්ණතා විශ්ලේෂණය  

කාල සංකීර්ණත්වය

ඕ (n * m) එහිදී n යනු නූල් ගණන සහ m යනු උපරිම නූලෙහි දිග වේ. මෙන්න අපි සෑම චරිතයක්ම බලන්නෙමු, ඒ නිසා කාල සංකීර්ණතාව O (n * m) වේ.

මෙයද බලන්න
ද්විමය නූලක් විකල්ප x සහ y සිදුවීම් ලෙස නැවත සකස් කරන්න

අභ්‍යවකාශ සංකීර්ණතාව

O (m * logn) මක් නිසාද යත්, එහි ප්‍රති ing ලයක් ලෙස ඇති නූල් හෝ දීර් est තම උපසර්ගය නූල ගබඩා කිරීම නිසා අපි ඉඩ වෙන් කරන්නේ O (m * logn) ය.