ধরুন আমাদের কাছে শুধুমাত্র ছোট হাতের অক্ষর সহ একই দৈর্ঘ্যের দুটি স্ট্রিং P এবং Q আছে, নীচের ক্রিয়াকলাপগুলি প্রয়োগ করার পরে স্ট্রিং Q এর সমান করার জন্য আমাদের স্ট্রিং P-এ ন্যূনতম সংখ্যক প্রাক-প্রসেসিং পদক্ষেপগুলি গণনা করতে হবে -
-
যেকোনো সূচক i নির্বাচন করুন এবং অক্ষর অদলবদল করুন pi এবং qi।
-
যেকোনো ইনডেক্স i নির্বাচন করুন এবং pi এবং pn – i – 1 অক্ষর অদলবদল করুন।
-
যেকোনো সূচক i নির্বাচন করুন এবং qi এবং qn – i – 1 অক্ষর অদলবদল করুন।
দ্রষ্টব্য − পরিসরে i এর মান (0 ≤ i
এক পদক্ষেপে আমরা ইংরেজি বর্ণমালার অন্য যেকোনো অক্ষরের সাথে P-এর একটি অক্ষর পরিবর্তন করতে পারি।
সুতরাং, যদি ইনপুটটি P =“pqprpqp”, Q =“qprpqpp” এর মত হয়, তাহলে আউটপুট 4 হবে যেমন আমরা P0 ='q', P2 ='r', P3 ='p' এবং P4 =' সেট করেছিলাম। q' এবং P হবে "qqrpqqp"। এর পরে আমরা নিম্নলিখিত ক্রিয়াকলাপগুলির ক্রম অনুসারে সমান স্ট্রিং পেতে পারি:swap(P1, Q1) এবং swap(P1, P5)৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=P
এর আকার -
res :=0
-
0 থেকে n / 2 রেঞ্জের জন্য, করুন
-
my_map :=একটি নতুন মানচিত্র
-
my_map[P[i]] :=1
-
যদি P[i] P[n - i - 1] এর মত হয়, তাহলে
-
my_map[P[n - i - 1]] :=my_map[P[n - i - 1]] + 1
-
-
যদি Q[i] my_map-এ থাকে, তাহলে
-
my_map[Q[i]] :=my_map[Q[i]] + 1
-
-
অন্যথায়,
-
my_map[Q[i]] :=1
-
-
যদি Q[n - i - 1] থাকে my_map-এ, তাহলে
-
my_map[Q[n - 1 - i]] :=my_map[Q[n - 1 - i]] + 1
-
-
অন্যথায়,
-
my_map[Q[n - 1 - i]] :=1
-
-
সাইজ :=আমার_ম্যাপের আকার
-
যদি আকার 4 এর মতো হয়, তাহলে
-
res :=res + 2
-
-
অন্যথায় যখন আকার 3 এর মতো হয়, তখন
-
res :=res + 1 + (1 যখন (P[i] P[n - i - 1] এর মত হয়), অন্যথায় 0)
-
-
অন্যথায় যখন আকার 2 এর মতো হয়, তখন
-
res :=res + my_map[P[i]] 2
এর মত নয়
-
-
-
যদি n mod 2 1 এর মত হয় এবং P[n / 2] Q[n / 2] এর মত না হয়, তাহলে
-
res :=res + 1
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def count_preprocess(P, Q): n = len(P) res = 0 for i in range(n // 2): my_map = dict() my_map[P[i]] = 1 if P[i] == P[n - i - 1]: my_map[P[n - i - 1]] += 1 if Q[i] in my_map: my_map[Q[i]] += 1 else: my_map[Q[i]] = 1 if Q[n - i - 1] in my_map: my_map[Q[n - 1 - i]] += 1 else: my_map[Q[n - 1 - i]] = 1 size = len(my_map) if (size == 4): res += 2 elif (size == 3): res += 1 + (P[i] == P[n - i - 1]) elif (size == 2): res += my_map[P[i]] != 2 if (n % 2 == 1 and P[n // 2] != Q[n // 2]): res += 1 return res A = "pqprpqp" B = "qprpqpp" print(count_preprocess(A, B))
ইনপুট
"pqprpqp", "qprpqpp"
আউটপুট
4