পাইথনে টেক্সটে প্যাটার্ন ম্যাচ করলে বোল্ড ট্যাগ দিয়ে হাইলাইট করা

সমস্যা বিবরণ

একটি টেক্সট এবং প্যাটার্ন লিস্ট দেওয়া আছে। টেক্সটে যেকোনো প্যাটার্ন ম্যাচ করলে সেটিকে <b> এবং </b> ট্যাগ দিয়ে র‍্যাপ করুন। ওভারল্যাপ বা এডজাসেন্ট প্যাটার্ন হলে সেগুলো মার্জ করে একই ট্যাগে রাখুন।

উদাহরণ

Input:  text = "thisissampleline"
        patterns = ["this", "ssam", "sample"]
Output: "thisissampleline"

অ্যালগরিদম

1. bold বুলিয়ান অ্যারে তৈরি করুন (টেক্সট দৈর্ঘ্যের সমান)
2. প্রতিটি ইনডেক্স i এবং প্যাটার্ন p এর জন্য:
   • যদি text[i:].startswith(p) হয়, তবে i থেকে i+len(p)-1 ইনডেক্স True করুন
3. ফাইনাল স্ট্রিং বানান:
   • bold[i] True এবং (i==0 বা bold[i-1]==False) হলে <b> যোগ করুন
   • ক্যারেক্টার যোগ করুন
   • bold[i] True এবং (i==n-1 বা bold[i+1]==False) হলে </b> যোগ করুন

পাইথন কোড

class Solution:
    def solve(self, text, patterns):
        n = len(text)
        bold = [False] * n
        
        # প্যাটার্ন ম্যাচ করা এলিমেন্টগুলো True মার্ক করুন
        for i in range(n):
            for p in patterns:
                if text[i:].startswith(p):
                    for j in range(len(p)):
                        if i + j < n:
                            bold[i + j] = True
        
        # রেজাল্ট স্ট্রিং বানান
        ans = ""
        for i in range(n):
            if bold[i] and (i == 0 or not bold[i - 1]):
                ans += ""
            ans += text[i]
            if bold[i] and (i == n - 1 or not bold[i + 1]):
                ans += ""
        
        return ans

ob = Solution()
text = "thisissampleline"
patterns = ["this", "ssam", "sample"]
print(ob.solve(text, patterns))
# thisissampleline

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n × m × k) — n = টেক্সট দৈর্ঘ্য, m = প্যাটার্ন সংখ্যা, k = গড় প্যাটার্ন দৈর্ঘ্য
• স্থান জটিলতা: O(n) — bold অ্যারে
• অপ্টিমাইজেশন: Aho-Corasick অ্যালগরিদম (O(n + m + k))

বাস্তব ব্যবহার

• সার্চ হাইলাইটিং (গুগল সার্চ রেজাল্টের মতো)
• কোড এডিটর সিনট্যাক্স হাইলাইটিং
• টেক্সট এডিটরে ফাইন্ড-রিপ্লেস প্রিভিউ

উপসংহার

• বুলিয়ান অ্যারে দিয়ে ওভারল্যাপ হ্যান্ডলিং সহজ
• সিম্পল ইমপ্লিমেন্টেশন, ছোট ইনপুটের জন্য ঠিক
• বড় টেক্সট/অনেক প্যাটার্নের জন্য Trie/Aho-Corasick ব্যবহার করুন