Palindromu bir axında yoxlamaq üçün onlayn alqoritm

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Çiy kərpic Zenefits
Palindrom Nümunə axtarışı SimBaxılıb 487

Problem bəyanat

"Palindromun bir axında yoxlanılması üçün onlayn alqoritm" problemində simvol axını verdik (karikaturaçılar bir-bir alınır). Alınan simvollar bu günə qədər formalaşarsa hər dəfə 'bəli' yazdıracaq bir proqram yazın palindrom.

Giriş Formatı

A olan ilk və yalnız bir sətir sim s.

Çıxış formatı

Karakterə görə keçin və “YES” yazdırın, əgər cari sətir (bu sətrə qədər bütün işarələr tərəfindən əmələ gəlmişsə), başqa bir halda “YOX” yazdır.

Məhdudiyyətlər

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

misal

bcdcb
YES  
NO 
NO 
NO   
YES

Explanation: İ = 0 üçün YES yaz, çünki “b” palindromdur. İ = 1 olarsa, NO yazdırın, çünki “bc” palindrom deyil. İ = 2 üçün NO yazdırın, çünki “bcd” palindrom deyil. Əgər i = 3 olarsa, NO yazdırın, çünki “bcdc” palindrom deyil. Və i = 4 üçün YES yaz, çünki “bcdcb” palindromdur.

Palindromun bir axında yoxlanılması üçün onlayn alqoritm üçün yanaşma

Əsas fikir budur ki, giriş sətrindəki hər bir simvol üçün s [0..i] nin palindrom olub olmadığını yoxlayın. Başqa bir metodda (optimal) əsas fikir, Rabin Karp alqoritmində istifadə olunan Rolling hash fikirindən istifadə etməkdir, çünki növbəti hash dəyəri əvvəlki O (1) vaxtından hesablana bilər. Hər indeks üçün birinci yarının və ikinci yarının əksini izləyin

Alqoritm

1. Birinci simvol həmişə palindromdur, buna görə ilk simvol üçün yes yazdırın.

2. Birinci hissənin tərsini birinci xarakterə, ikinci yarıyı ikinci simvoluna başlayın. Birinci yarının ters çevrilməsi 'FR', ikinci yarınınki 'S' olsun.

3. Simli ikinci simvoldan keçin

  • 'FR' və 'S' eynidirsə, iff s [0..i] 'nin simvol uyğunluğu ilə sadə bir simvol istifadə edərək palindrom olduğunu yoxlayın
  • Növbəti təkrarlama üçün 'FR' və 'S' düymələrini yeniləyin.
  • 'İ' bərabərdirsə, növbəti işarəni 'FR' başlanğıcına və ikinci yarının sonuna əlavə edin və hash dəyərlərini yeniləyin.
  • 'İ' təkdirsə, 'FR' olduğu kimi saxlayın, aparıcı simvolu ikincidən kənarlaşdırın və sonunda növbəti işarəni əlavə edin.

Yuxarıda göstərilən alqoritmin tətbiqi

s = "bcdcb"
FR və S. başlatma FR = hash ("b"), S = hash ("c")
İkinci xarakterdən keçin
i = 1, FR və S bərabər deyil, buna görə NO yazdırın.
yeniləmə FR və S, i tək olduğu üçün FR dəyişdirilməyəcək və S hash olur (“d”)
i = 2, FR və S bərabər deyil, buna görə NO yazdırın.
yeniləmə FR və S, i belədir ki, FR hash ("cb") olur və S hash olur ("dc")
i = 3, FR və S bərabər deyil, buna görə NO yazdırın.
yeniləmə FR və S, i tək olduğu üçün FR dəyişdirilməyəcək və S hash olur (“cb”)
i = 4, FR və S uyğun gəlir, buna görə YES yazdırın.
Son indeks olduğu üçün yeniləməyə ehtiyac yoxdur

Həyata keçirilməsi

Palindromun bir axında yoxlanılması üçün onlayn alqoritm üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
// p is a prime number used for evaluating Rabin Karp's Rolling hash
#define p 103
 
void isPalindrome(string s)
{
    // Length of input string
    int N = s.length();
 
    // first character is a palindrome
    cout<<"YES"<<endl;
 
    // Return if string has only one character
    if (N == 1) return;
 
    // Initialize first half reverse and S half for 
    // as FR and S characters
    int FR  = s[0] % p;
    int S = s[1] % p;
 
    int h = 1, i, j;
 
    // Now check for palindromes from S character
    // onward
    for (i=1; i<N; i++)
    {
        // If the hash values of 'FR' and 'S' 
        // match, then only check individual characters
        if (FR == S)
        {
            //check if s[0..i] is a palindorme
            for (j = 0; j < i/2; j++)
            {
                if (s[j] != s[i-j])
                    break;
            }
            if((j == i/2))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        { 
            cout<<"NO"<<endl;
        }

        //update hash values
        if (i != N-1)
        {
            // If i is even (next i is odd) 
            if (i%2 == 0)
            {
                // Add next character after first half at beginning 
                // of 'FR'
                h = (h*NO_OF_CHARS) % p;
                FR  = (FR + h*s[i/2])%p;
                 
                // Add next character after S half at the end
                // of S half.
                S = (S*NO_OF_CHARS + s[i+1])%p;
            }
            else
            {
                // If i is odd (next i is even) then we
                // need not update FR, we need to remove
                // first character of S and append a
                // character to it.
                S = (NO_OF_CHARS*(S + p - s[(i+1)/2]*h)%p
                          + s[i+1])%p;
            }
        }
    }
}
 
int main()
{
    string s;
    cin>>s;
    isPalindrome(s);
    return 0;
}

Palindromun bir axında yoxlanılması üçün onlayn alqoritm üçün Java proqramı

import java.util.Scanner;
class sum
{
    private static int p=103;
    private static int NO_OF_CHARS = 256;
    public static void isPalindrome(String s)
    {
        // Length of input string
        int N = s.length();

        // first character is a palindrome
        System.out.println("YES");

        // Return if string has only one character
        if (N == 1) return;

        // Initialize first half reverse and S half for 
        // as FR and S characters
        int FR  = s.charAt(0) % p;
        int S = s.charAt(1) % p;

        int h = 1, i, j;

        // Now check for palindromes from S character
        // onward
        for (i=1; i<N; i++)
        {
            // If the hash values of 'FR' and 'S' 
            // match, then only check individual characters
            if (FR == S)
            {
                //check if s[0..i] is a palindorme
                for (j = 0; j < i/2; j++)
                {
                    if (s.charAt(j) != s.charAt(i-j))
                        break;
                }
                if((j == i/2))
                {
                    System.out.println("YES");
                }
                else
                {
                    System.out.println("NO");
                }
            }
            else
            { 
                System.out.println("NO");
            }

            //update hash values
            if (i != N-1)
            {
                // If i is even (next i is odd) 
                if (i%2 == 0)
                {
                    // Add next character after first half at beginning 
                    // of 'FR'
                    h = (h*NO_OF_CHARS) % p;
                    FR  = (FR + h*s.charAt(i/2))%p;

                    // Add next character after S half at the end
                    // of S half.
                    S = (S*NO_OF_CHARS + s.charAt(i+1))%p;
                }
                else
                {
                    // If i is odd (next i is even) then we
                    // need not update FR, we need to remove
                    // first character of S and append a
                    // character to it.
                    S = (NO_OF_CHARS*(S + p - s.charAt((i+1)/2)*h)%p
                              + s.charAt(i+1))%p;
                }
            }
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        isPalindrome(s);
    }
    
}
abacbca
YES
NO
YES
NO
NO
NO
NO

Palindromun bir axında yoxlanılması üçün onlayn alqoritm üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * n) hara n verilən sətrin ölçüsüdür. Burada n * n ən pis zaman mürəkkəbliyidir. Ancaq ümumiyyətlə, əsas sadə yanaşmadan daha yaxşı işləyir. Əvvəlcə hash dəyərlərini müqayisə edərək tam substring müqayisəsindən çəkinirik. Ən pis vəziyyət “zzzzzzzzz” kimi eyni simvollara sahib giriş sətirləri üçün baş verir.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerimiz yoxdur.

Translate »