[알고리즘 기초] Trie 알고리즘
문자열 집합 을 유지 하고 두 가지 동작 을 지원 합 니 다.
총 N 개의 동작 이 있 습 니 다. 입력 한 문자열 의 총 길 이 는 초과 하지 않 습 니 다. 105105, 문자열 은 소문 자 만 포함 합 니 다.
입력 형식
첫 줄 은 정수 N 을 포함 하고 조작 수 를 표시 합 니 다.
다음 N 줄 은 각 줄 에 하나의 조작 명령 을 포함 하고 명령 은 'I x' 또는 'Q x' 중의 하나 입 니 다.
출력 형식
모든 질문 명령 'Q x' 에 대해 하나의 정 수 를 결과 로 출력 하여 x 가 집합 에서 나타 나 는 횟수 를 나타 낸다.
결과 마다 한 줄 을 차지한다.
데이터 범위
1≤N≤2∗1041≤N≤2∗104
입력 예시:
5
I abc
Q abc
Q ab
I ab
Q ab
출력 예시:
1
0
1
생각:
Trie 알고리즘 은 문자열 을 효율적으로 저장 하고 읽 을 수 있 으 며 트 리 의 구 조 를 활용 하여 중복 되 는 저장 소 를 줄 일 수 있 습 니 다.
자세 한 코드 분석:
#include
#include
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char str[]) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - '0';// a b c .... 。
if (!son[p][u]) son[p][u] = ++idx;// 。
p = son[p][u];//
}
cnt[p] ++;// 1， 。
}
int query(char str[]) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - '0';
if (!son[p][u]) return 0;// ，
p = son[p][u];
}
return cnt[p];// 。
}
int main() {
char op[2];
int t;
scanf("%d", &t);
while (t--) {
scanf("%s%s", op, str);
if (op[0] == 'I') insert(str);
else printf("%d
", query(str));
}
return 0;
} 배 운 것 은 이 문 제 를 볼 수 있다.https://www.cnblogs.com/Attacking-vincent/p/13041621.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
