이 문제에서는 크기가 n인 텍스트와 크기가 m인 패턴 두 개의 문자열이 제공됩니다. 우리의 임무는 Anagram 부분 문자열 검색을 위한 프로그램을 만드는 것입니다.
여기서 우리는 텍스트에서 패턴의 모든 발생과 모든 순열(아나그램)을 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
text = “xyztrwqyzxfg” pattern = “xyz”
출력
Found at index 0 Found at index 7
이 문제를 해결하려면 Rabin Karp 알고리즘과 유사한 알고리즘을 사용해야 합니다. 숫자의 모듈로 아래 모든 문자의 ASCII 값을 추가하여 아나그램 발생 여부를 확인하는 데 사용됩니다. 그런 다음 특성 세트 창을 사용하고 합계를 일치시킵니다.
솔루션에는 텍스트 창의 문자 빈도와 일치하는 패턴을 저장할 두 개의 배열이 필요합니다. 그런 다음 창을 하나씩 슬라이드하고 각 창의 문자 빈도를 일치시키고 일치하는 패턴의 인쇄를 인쇄합니다.
Anagram 부분 문자열 검색을 위한 프로그램
//애너그램 부분 문자열 검색을 위한 프로그램
예시
#include <cstring>
#include <iostream>
#define MAX 256
using namespace std;
bool matchPattern(char arr1[], char arr2[]){
for (int i = 0; i < MAX; i++)
if (arr1[i] != arr2[i])
return false;
return true;
}
void anagramSearch(char* pattern, char* text){
int M = strlen(pattern);
int N = strlen(text);
char patternArray[MAX] = { 0 }, textArray[MAX] = { 0 };
for (int i = 0; i < M; i++) {
(patternArray[pattern[i]])++;
(textArray[text[i]])++;
}
for (int i = M; i < N; i++) {
if (matchPattern(patternArray, textArray))
printf("\nPattern found at index value : %d", (i-M));
(textArray[text[i]])++;
textArray[text[i - M]]--;
}
if (matchPattern(patternArray, textArray))
printf("\nPattern found at index value: %d", (N-M));
}
int main() {
char text[] = "xyztrwqyzxfg";
char pattern[] = "xyz";
printf("Searching Anagram pattern in the string ");
anagramSearch(pattern, text);
return 0;
} 출력
Searching Anagram pattern in the string Pattern found at index value: 0 Pattern found at index value: 7