Simli palindrom etmək üçün ön tərəfə əlavə ediləcək minimum simvollar

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Məlumat dəsti google microsoft SAP SAP Laboratoriyaları
SimBaxılıb 404

Problem bəyanat

“Simli palindrom etmək üçün ön tərəfə əlavə ediləcək minimum simvollar” problemində a sim "S". Simli palindrom etmək üçün önə əlavə ediləcək minimum simvolları tapmaq üçün bir proqram yazın.

Giriş Formatı

Simli olan ilk və yalnız bir sətir "S".

Çıxış formatı

Tamsayı dəyəri olan ilk və yalnız bir sətir n. Burada n simli palindrom etmək üçün ön tərəfə əlavə ediləcək minimum simvolları göstərir.

Məhdudiyyətlər

  • 1 <= | s | <= 10 ^ 6
  • s [i] kiçik İngilis əlifbası olmalıdır

misal

edef
1

Explanation: "S" simlinin ön hissəsinə "f" əlavə etsək, o zaman ipimiz palindromun vəziyyətini təmin edir. Beləliklə, burada ön tərəfə yalnız 1 əlavə olunmalıdır.

Alqoritm

1. Sətri xüsusi bir simvolla birləşdirin və verilmiş sətrin tərsinə, yəni c = s + $ + rs

2. Hər bir indeksin eyni zamanda bir şəkilçi olan ən uzun düzgün prefiksi təmsil etdiyi bir LPS seriyası yaradın.

3. LPS massivindəki son dəyər orijinal sətrin əvvəlinə uyğun gələn ən böyük şəkilçidir. Beləliklə, palindrom xüsusiyyətini təmin edən bir çox simvol var

4. İndi simli uzunluğu ilə LPS massivindəki son dəyər arasındakı fərqi tapın, bu simli palindrom etmək üçün lazım olan minimum simvol sayıdır.

Yuxarıdakı nümunənin işlənməsi

s = "edef"

Düzgün prefiks və şəkilçi üçün nümunə (LPS əmələ gətirmək üçün tələb olunan bilik)

Düzgün “abc” önekləri “”, “a”, “ab” və “abc” şəkilçiləri “c”, “bc”, “abc” dir.

s (birləşmədən sonra) = “edef $ fede”

LPS = {0, 0, 1, 0, 0, 0, 1, 2, 3} // Burada indeks şəkilçiyə uyğun gələn ən böyük prefiksin ən uzun uzunluğudur.

Son dəyər LPS = 3, buna görə palindrom xüsusiyyətini təmin edən 3 simvol var.

İndi verilmiş bir sətrin uzunluğu (yəni 4) ilə Son dəyər (3) arasındakı fərqi tapın

Buna görə palindrom etmək üçün 1 simvol lazımdır.

Həyata keçirilməsi

Simli palindrom etmək üçün ön tərəfə əlavə ediləcək minimum simvollar üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
 
vector<int> computeLPSArray(string s)
{
    int n = s.length();
    vector<int> LPS(n);
 
    int len = 0;
    LPS[0] = 0; 
    int i = 1;
    while (i < n)
    {
        if (s[i] == s[len])
        {
            len++;
            LPS[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = LPS[len-1];
            }
            else 
            {
                LPS[i] = 0;
                i++;
            }
        }
    }
    return LPS;
}

int solve(string s)
{
    string rs = s;
    reverse(rs.begin(), rs.end());
    string c = s + "$" + rs;
    vector<int> LPS = computeLPSArray(c);
    return (s.length() - LPS.back());
}
 
int main()
{
    string s;
    cin>>s;
    cout<<solve(s)<<endl;
    return 0;
}

Simli Palindrom etmək üçün Önə Əlavə Ediləcək Minimum Simvollar üçün Java proqramı

import static java.lang.Math.abs;
import java.util.Scanner;

class sum
{ 
        public static int[] computeLPSArray(String str) 
        { 
            int n = str.length(); 
            int lps[] = new int[n]; 
            int i = 1, len = 0; 
            lps[0] = 0;
            while (i < n)  
            { 
                if (str.charAt(i) == str.charAt(len)) 
                { 
                    len++; 
                    lps[i] = len; 
                    i++; 
                } 
                else
                { 
                    if (len != 0) 
                    { 
                        len = lps[len - 1];  
                    } 
                    else
                    { 
                        lps[i] = 0; 
                        i++; 
                    } 
                } 
            } 
            return lps; 
        } 
        static int solve(String str)  
        {  
            StringBuilder s = new StringBuilder(); 
            s.append(str); 
            String rev = s.reverse().toString(); 
            s.reverse().append("$").append(rev); 
            int lps[] = computeLPSArray(s.toString()); 
            return str.length() - lps[s.length() - 1]; 
        } 

  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                System.out.println(solve(s));
  } 
} 
qsjhbqd
6

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilən sətrin ölçüsüdür "S". Burada hesablama üçün xətti vaxt aparan “lps KMP alqoritmi massivi” ni tapırıq.

Kosmik Mürəkkəblik

O (n) çünki cavabımızı hesablamaq üçün bir LSP dizisi yaradırıq. Və burada LSP dizisinin maksimum ölçüsüdür n.

Translate »