K uzunluğunda bir alt sətrin təkrarı olan bir simli çevirin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Çiy kərpic American Express Verilənlər bazası Pulsuz yükləmə
Sükut Hashing HashMap SimBaxılıb 200

Problem bəyanat

“K uzunluğunda bir alt sətrin təkrarı olan bir simli çevir” problemində a verdik sim “S” və “k” tam ədədi. Bunu k simvollu bir alt sətrin təkrarı olan bir sətrə çevirmək mümkün olub olmadığını yoxlamaq üçün bir proqram yazın.

Giriş Formatı

"S" simli olan ilk sətir.

"K" tam ədədi olan ikinci sətir.

Çıxış formatı

K simvollu bir alt sətrin təkrarı olan bir sətirə çevirmək mümkündürsə, "YES" yazdırın. Əks təqdirdə “YOX” yazdırın.

Məhdudiyyətlər

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

misal

abcdefabc
3
YES

Explanation: Burada “def” i “abc” ilə əvəz edə bilərik. O zaman yenilənmiş simlərimiz “abcabcabc” dir. İndi, abc'u üç dəfə birləşdirib bağlamadığımızı asanlıqla görə bilərik, sonra bu simli əldə edirik.

acdaacda
2
NO

Explanation: 2 uzunluğunda heç bir alt sətir yoxdur ki, onu dəyişdirib düzəldə bilərik ki, k uzunluğundakı alt sətrin birləşməsi ilə əldə edək.

Alqoritm

1. Simdən keçin və uzunluq k.m uzunluğundakı alt tellərin (0-dan k-1-ə, k-dan 2k-1-ə, 2k-dən 3k-1-ə və s.) Tezliyini ehtiva edən bir xəritə qurun.

2. K uzunluğundan yalnız iki fərqli alt tel varsa və alt sətirdən birinin sayı 1-dirsə, “YES” yazdırın.

3. Əks təqdirdə “YOX” yazdırın.

Həyata keçirilməsi

Uzunluqlu K Substringinin təkrarı olan bir simli çevirmək üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    string s;
    cin>>s;
    int k;
    cin>>k;
    int n=s.length();
    if(n%k!=0)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        unordered_map<string, int> m; 
        for (int i=0; i<n; i+=k) 
        {
            m[s.substr(i, k)]++;
        }
        if(m.size()==1)
        {
            cout<<"YES"<<endl;
        }
        else if(m.size()==2)
        {
            if(m.begin()->second==1 || m.begin()->second==(n/k-1))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0; 
}

K uzunluğunda bir alt sətrin təkrarı olan bir simli çevirmək üçün Java proqramı

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k = sr.nextInt();
                int n=s.length();
                if(n%k!=0)
                {
                    System.out.println("NO");
                }
                else
                {
                    HashMap<String, Integer> m = new HashMap<>();
                    for(int i=0;i<n;i+=k)
                    {
                        String x = s.substring(i,i+k);
                        int temp = m.get(s.substring(i,i+k))==null? 0 : m.get(s.substring(i,i+k));
                        m.put(s.substring(i,i+k), temp+1);
                    }
                    if(m.size()==1)
                    {
                        System.out.println("YES");
                    }
                    else if(m.size()==2)
                    {
                        int flag=0;
                        for(Map.Entry<String, Integer> e : m.entrySet())
                        {
                            if(e.getValue()==1)
                            {
                                flag=1;
                                break;
                            }
                        }
                        if(flag==0)
                        {
                            System.out.println("NO");
                        }
                        else
                        {
                            System.out.println("YES");
                        }
                    }
                    else
                    {
                        System.out.println("NO");
                    }
                }
  } 
} 
abcdabab
YES

K uzunluğunda bir alt sətrin təkrarı olan bir simli çevirmək üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilən "s" sətrinin ölçüsüdür. Burada sadəcə (0-dan k-1-ə, k-dan 2k-1-ə, 2k-dən 3k-1-ə və s.) Ok k uzunluğu əmələ gətiririk və hash map istifadə edərək tezliklərini sayırıq. Burada biz xətti vaxtda edirik.

Kosmik Mürəkkəblik

O (n) hara n verilən "s" sətrinin ölçüsüdür. Burada uzunluq k alt sətirinin sayını saxlamaq üçün hash xəritəsi istifadə edirik.

Translate »