[C] Anagram Search
Codeforces Round #103 (Div. 2)
anagram 인지를 확인하면 되므로
문자열 매칭을 할 필요는 없고, 알파벳 별 개수만 갖고 확인할 수 있다.
sliding window 로
문자열p를 문자열s의 처음부터 대조하면서 오른쪽으로 나아가면 된다.
현재 s_i = s[i..i+|p|-1] 을 대조하고 있다고 했을 때
count(p, c) > count(s_i, c) 인 알파벳 c가 존재한다면
그 부분은 anagram이 될 가능성이 없는 것이다.
만약 이렇지 않다면 '?'를 적절히 치환하여 anagram으로 항상 만들 수 있다.
window를 오른쪽으로 한칸 옮길 때
count 함수를 일일히 갱신하는 것이 아니라
방금 window에서 빠지게 된 문자, 방금 window로 들어오게 된 문자
두가지만 +-1 을 해주면 된다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <vector> | |
| #include <string> | |
| using namespace std; | |
| char buf[100005]; | |
| int main() { | |
| scanf("%s", buf); | |
| string s(buf); | |
| scanf("%s", buf); | |
| string p(buf); | |
| vector<int> pcnt(26); | |
| for (char c : p) pcnt[c - 'a'] += 1; | |
| int ans = 0; | |
| vector<int> nowcnt(26); | |
| for (int i = 0, j = 0; i + p.length() <= s.length(); ++i) { | |
| while (j < i + p.length()) { | |
| if (s[j] != '?') nowcnt[s[j] - 'a'] += 1; | |
| ++j; | |
| } | |
| bool ok = true; | |
| for (int k = 0; k < 26; ++k) { | |
| if (pcnt[k] < nowcnt[k]) { | |
| ok = false; | |
| break; | |
| } | |
| } | |
| if (ok) ans += 1; | |
| if (s[i] != '?') nowcnt[s[i] - 'a'] -= 1; | |
| } | |
| printf("%d\n", ans); | |
| return 0; | |
| } |