LeetCoding Challenge - Find All Anagrams in a String
문자열 S와 P가 주어지는데, S의 연속 부분 문자열 중 P와 애너그램 관계인 문자열의 시작 인덱스를 모두 담은 벡터를 반환하는 문제입니다.
길이가 N인 문자열의 애너그램 개수는 N! 개이므로 모든 애너그램에 대해 판별하는 것은 조금 무리가 있어보입니다.
그렇다면 애너그램 전부에 대해 값이 같은 방식의 해싱을 사용해서 비교하면 어떨까요?
이런 해싱 중 가장 쉽게 떠올릴 수 있는 건 연속한 len(P)개의 문자의 아스키코드 값을 모두 곱하면 문자의 배치 순서와는 무관하고, 구성하는 문자들에만 영향을 받기 때문에 애너그램들이 모두 같은 값을 갖게 됩니다.
길이가 20100까지이므로 숫자가 커질 수 있으니, 적당하게 큰 소수를 골라 나머지를 취해줍시다.
S의 연속한 len(P)개의 문자의 해싱 값을 구하는 것은 정수론과 스위핑을 사용하여 $O(len(S))$에 모두 가능합니다.
class Solution {
public:
const long long mod=1000012309ll;
long long ipow(long long a,long long b){
if(b==1)return a;
if(b==0)return 1;
long long x=ipow(a*a%mod,b/2);
if(b&1)x=x*a%mod;
return x;
}
vector<int> findAnagrams(string s, string p) {
if(s.size()<p.size())return vector<int>();
for(char& i:s)i-='a'-2;
for(char& i:p)i-='a'-2;
long long x=1;
for(char i:p){
x*=i;
x%=mod;
}
vector<int> v;
long long k=1;
for(int i=0;i<p.size();i++){
k*=s[i];
k%=mod;
}
if(k==x)v.push_back(0);
for(int i=p.size();i<s.size();i++){
k*=ipow(s[i-p.size()],mod-2);
k%=mod;
k*=s[i];
k%=mod;
if(k==x)v.push_back(i-p.size()+1);
}
return v;
}
};