Najdłuższy wspólny prefiks słowo po dopasowaniu słów

Poziom trudności Ciężko
Często zadawane pytania Adobe Amazonka Apple Bloomberg eBay Facebook Google Microsoft VMware Yahoo
sznurodwiedzajacy 292

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W zadaniu „Najdłuższy wspólny prefiks używający słowa według dopasowania słów” daliśmy N smyczki. Napisz program, który znajdzie najdłuższy wspólny prefiks podanych ciągów.

Format wejściowy

Pierwszy wiersz zawierający liczbę całkowitą N, która oznacza liczbę ciągów.

Następne N wierszy zawierających ciąg.

Format wyjściowy

Pierwsza i jedyna linia zawierająca ciąg „ans”, który jest naszym najdłuższym wspólnym prefiksem z podanych N ciągów. Jeśli taki przedrostek nie istnieje, wypisz -1.

ograniczenia

  • 1 <= | N | <= 10 ^ 3
  • 1 <= | s [i] | <= 10 ^ 3 gdzie i od 0 do N-1
  • s [i] [j] musi być alfabetem angielskim małą literą, gdzie i od 0 do N-1, a j od 0 do | s [i] |.

Przykład

5
abcde 
abba 
abaa 
abbbbb 
ababab
ab

Wyjaśnienie: Tutaj widzimy, że wspólnym przedrostkiem pierwszego i drugiego łańcucha jest „ab”. Teraz sprawdź ten prefiks z każdym ciągiem jeden po drugim i uzyskaj ostatni przedrostek, którym jest „ab”.

Algorytm

Tutaj używamy właściwości Associate - LCP (s1, s2, s3) = LCP (LCP (s1, s2), s3). Aby zastosować ten pomysł, algorytm wykonuje iterację w łańcuchach [S1… Sn], znajdując się w każdej iteracji  najdłuższy wspólny prefiks ciągów  Gdy  jest pustym łańcuchem, algorytm się kończy. W przeciwnym razie po n iteracje, algorytm zwraca .

1.  Tworzymy funkcję, aby znaleźć wspólny przedrostek dla dwóch ciągów.

  • Porównaj znaki w łańcuchach.
  • Popchnij je do wyniku, jeśli to samo.
  • Zwróć wynik końcowy.

2. Ustaw początkowy przedrostek output_prefix jako pierwszy element ciągu wejściowego.

3. Porównaj go z drugim i zapisz w ouput_prefix i tak dalej.

4. Zwraca końcowy parametr output_prefix.

Realizacja

Program C ++ dla najdłuższego wspólnego prefiksu słowo według dopasowania słów

#include <bits/stdc++.h>
using namespace std;
 
string prefix(string s, string t)
{
    string res;
    int n = s.length();
    int m = t.length();
    for(int i=0,j=0;(i<=n-1)&&(j<=m-1);i++,j++)
    {
        if(s[i]!=t[j])
        {
            break;
        }
        res.push_back(s[i]); 
    }
    return res;
}

string  common_prefix(vector<string> v)
{
    string res=v[0];
    for(int i=1;i<=v.size()-1;i++)
    {
        res=prefix(res,v[i]);
    }
    return res;
}
 
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;
}

Program w języku Java z najdłuższym wspólnym prefiksem słowo według dopasowania słów

import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static String prefix(String s, String t)
    {
        String res="";
        int n = s.length();
        int m = t.length();
        for(int i=0,j=0;(i<n)&&(j<m);i++,j++)
        {
            if(s.charAt(i)!=t.charAt(j))
            {
                j=m;
            }
            else
            {
                res+=(s.charAt(i));
            } 
        }
        return res;
    }
    public static String common_prefix(Vector<String> v)
    {
        String res=v.get(0);
        for(int i=1;i<=v.size()-1;i++)
        {
            res=prefix(res, v.get(i));
        }
        return res;
    }
    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 
abba 
abaa 
abbbbb 
ababab
ab

Analiza złożoności dla najdłuższego wspólnego prefiksu słowo według dopasowania słów

Złożoność czasowa

O (n * m) gdzie n to całkowita liczba ciągów i m jest długością maksymalnego ciągu.

Złożoność przestrzeni

O (m) do przechowywania wspólnego przedrostka po wykonaniu operacji między dwoma ciągami.

Wywiady dotyczące projektowania systemu pękania
Translate »