অ্যানাগ্রাম হলো একটি স্ট্রিং বা প্যাটার্নের সব পমুটেশন। এই অ্যালগরিদমে শুধু একজ্যাক্ট প্যাটার্ন নয়, প্যাটার্নের সব সম্ভাব্য অ্যারেঞ্জমেন্ট টেক্সটে সার্চ করা হয়।
সমাধান: টেক্সটকে প্যাটার্নের দৈর্ঘ্যের উইন্ডোতে ভাগ করে, প্রতিটি উইন্ডোর ক্যারেক্টার ফ্রিকোয়েন্সি কাউন্ট করে প্যাটার্নের ফ্রিকোয়েন্সি-এর সাথে মিলিয়ে দেখা হয়।
টাইম কমপ্লেক্সিটি: O(n)
ইনপুট এবং আউটপুট
Input: Main String: "AABAACBABBCABAABBA", Pattern: "AABC"
Output: Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10
অ্যালগরিদম
anagramSearch(text, pattern)
Begin
patternFreq[], stringFreq[] অ্যারে
patLen, strLen
patternFreq 0 করে, pattern-এর ফ্রিকোয়েন্সি বেড়ান
for i := 0 to strLen - patLen do
stringFreq 0 করে
for j := i to i+patLen-1: stringFreq[mainString[j]]++
if stringFreq == patternFreq: print i (anagram found)
done
End
C++ উদাহরণ
#include <iostream>
#include <cstring>
#define LETTER 26
using namespace std;
bool arrayCompare(int *a1, int *a2, int n) {
for(int i=0; iআউটপুট
Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10
