C++에서 문자열의 모든 아나그램 찾기

문자열 s와 비어 있지 않은 문자열 p가 있다고 가정하면 s에서 p의 아나그램의 모든 시작 인덱스를 찾아야 합니다. 문자열은 소문자로만 구성되며 문자열 s와 p의 길이는 20과 100보다 크지 않습니다. 따라서 예를 들어 s:"cbaebabacd" p:"abc"인 경우 출력은 [0, 6 ], 인덱스 0에 "cba", 다른 하나가 "bac", 이들은 "abc"의 아나그램입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 맵 정의 m, n :=s의 크기, 왼쪽으로 설정 :=0, 오른쪽으로 :=0, 카운터 :=p의 크기

• 배열 정의

• p의 문자 빈도를 맵 m에 저장

• 오른쪽:=0 ~ n – 1

  • m이 s[right]이고 m[s[right]]가 0이 아닌 경우 m[s[right]]를 1로 줄이고 counter를 1로 줄이고 counter =0이면 왼쪽을 ans에 삽입

  • 그렇지 않으면

    • 왼쪽 <오른쪽,

      동안

      • s[left]가 m에 없으면 카운터를 1만큼 증가시키고 m[s[left]]를 1만큼 증가시킵니다.

      • 왼쪽으로 1 증가

      • m이 s[right]이고 m[s[right]]가 0이 아닌 경우 오른쪽으로 1 감소하고 루프에서 나옵니다.

    • m에 s[left]가 없으면 left로 설정합니다. :=right + 1

• 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findAnagrams(string s, string p) {
      map <char, int> m;
      int n = s.size();
      int left = 0, right = 0;
      int counter = p.size();
      vector <int> ans;
      for(int i = 0; i < p.size(); i++) m[p[i]]++;
      for(int right = 0; right < n; right++){
         if(m.find(s[right]) != m.end() && m[s[right]]){
            m[s[right]]--;
            counter--;
            if(counter == 0)ans.push_back(left);
         } else {
            while(left<right){
               if(m.find(s[left]) != m.end()) {
                  counter++;
                  m[s[left]]++;
               }
               left++;
               if(m.find(s[right]) != m.end() && m[s[right]]){
                  right--;
                  break;
               }
            }
            if(m.find(s[left])==m.end())left = right + 1;
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.findAnagrams("cbaebabacd", "abc")) ;
}

입력

"cbaebabacd"
"abc"

출력

[0, 6, ]