Tirl - Trie 문자열 통계
9366 단어 데이터 구조
문자열 집합 을 유지 하고 두 가지 동작 을 지원 합 니 다.
"I x" 는 집합 에 문자열 x 를 삽입 합 니 다."Q x" 는 집합 에 문자열 이 몇 번 나 왔 는 지 물 어 봅 니 다.모두 N 개의 동작 이 있 습 니 다. 입력 한 문자열 의 총 길 이 는 105 를 넘 지 않 고 소문 자 만 포함 합 니 다.
입력 형식 첫 줄 은 정수 N 을 포함 하여 조작 수 를 표시 합 니 다.
다음 N 줄 은 각 줄 에 하나의 조작 명령 을 포함 하고 명령 은 'I x' 또는 'Q x' 중의 하나 입 니 다.
출력 형식 은 모든 질문 명령 'Q x' 에 대해 하나의 정 수 를 결과 로 출력 하여 x 가 집합 에서 나타 나 는 횟수 를 나타 낸다.
결과 마다 한 줄 을 차지한다.
데이터 범위 1 ≤ N ≤ 2 ∗ 1 0 4 1 ≤ N ≤ 2 ∗ 10 ^ 4 1 ≤ N ≤ 2 ∗ 104 5 I abc Q abc Q ab I ab Q ab 출력 사례: 1 0 1
#include
using namespace std;
char str[10005];
int son[10005][26],cnt,con[10005];
void insert(char str[])
{
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++cnt;
p=son[p][u];
}
con[p]++;
}
int query(char str[])
{
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return con[p];
}
int main()
{
int n; scanf("%d",&n);
for(int i=1;i<=n;i++){
char op[2];
scanf("%s",op);
if(op[0]=='I'){
scanf("%s",str);
insert(str);
}else {
scanf("%s",str);
printf("%d
",query(str));
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.