타이어 트 리 요약 (템 플 릿 + 예제)
제목 은 에서 나 왔 다.
Tire 트 리 는 문자열 을 빠르게 찾 을 수 있 는 데이터 구조 입 니 다.
템 플 릿
#include
#include
#include
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 1123;
int tire[MAXN][26], tot = 1;
bool end[MAXN];
void add(char* str)
{
int len = strlen(str), p = 1;
REP(i, 0, len)
{
int ch = str[i] - 'a'; // a 0
if(!tire[p][ch]) tire[p][ch] = ++tot;
p = tire[p][ch];
}
end[p] = true;
}
bool search(char* str)
{
int len = strlen(str), p = 1;
REP(i, 0, len)
if(!(p = tire[p][str[i] - 'a']))
return false;
return end[p];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
REP(i, 0, n)
{
char s[15];
scanf("%s", s);
add(s);
}
while(m--)
{
char s[15];
scanf("%s", s);
printf("%s
", search(s) ? "Yes": "No");
}
return 0;
}
예제
질문: n 개의 문자열 과 m 번 에 게 물 어 봅 니 다. 매번 주어진 문자열 T 를 물 어 볼 때마다 출력 에 몇 개의 문자열 이 T 의 접두사 인지 물 어 봅 니 다.
해답: 모든 문자열 을 추가 할 때 엔 딩 노드 에 1 을 추가 하고 T 후 Tire 트 리 에서 검색 한 다음 에 길 을 따라 문자열 이 끝 나 는 값 을 추가 하면 됩 니 다.중복 되 는 문자열 이 있 을 수 있 습 니 다.
#include
#include
#include
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 1123;
int tire[MAXN][26], tot = 1;
int end[MAXN]; //
void add(char* str)
{
int p = 1;
REP(i, 0, strlen(str))
{
int ch = str[i] - 'a';
if(!tire[p][ch]) tire[p][ch] = ++tot;
p = tire[p][ch];
}
end[p]++;
}
int search(char* str)
{
int p = 1, res = 0;
REP(i, 0, strlen(str))
{
if(!(p = tire[p][str[i] - 'a'])) break;
res += end[p];
}
return res;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
REP(i, 0, n)
{
char s[15];
scanf("%s", s);
add(s);
}
while(m--)
{
char s[15];
scanf("%s", s);
printf("%d
", search(s));
}
return 0;
}
hdu 1251
이전 문제 와 유사 하 다.
질문: n 개의 문자열 과 m 번 물 어 봅 니 다. 매번 T 문자열 을 물 어 볼 때마다 출력 T 는 몇 개의 문자열 의 접두사 입 니까?
해답: 각 노드 의 하위 트 리 (노드 자체 포함) 아래 에 몇 개의 문자 종점 이 있 는 지 dfs 에서 한 번 에 처리 할 수 있 습 니 다.
그리고 T 의 마지막 문 자 를 찾 아 예비 처리 결 과 를 출력 하면 됩 니 다.
이 문제 의 입력 이 비교적 번 거 로 우 니 주의 하여 * s 가 비어 있 는 지 아 닌 지 를 판단 하 세 요.
#include
#include
#include
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 1e6;
int tire[MAXN][26], d[MAXN], tot = 1;
bool End[MAXN];
void add(char* str)
{
int p = 1;
REP(i, 0, strlen(str))
{
int ch = str[i] - 'a';
if(!tire[p][ch]) tire[p][ch] = ++tot;
p = tire[p][ch];
}
End[p] = true;
}
int dfs(int p)
{
if(End[p]) d[p]++;
REP(ch, 0, 26)
{
if(tire[p][ch])
d[p] += dfs(tire[p][ch]);
}
return d[p];
}
int search(char* str)
{
int p = 1, res = 0;
REP(i, 0, strlen(str))
if(!(p = tire[p][str[i] - 'a'])) return 0;
return d[p];
}
int main()
{
char s[15];
while(gets(s) && *s) add(s);
dfs(1);
while(~scanf("%s", s)) printf("%d
", search(s));
return 0;
}
[예제] XOR 가장 큰 쌍
문제: n 개의 정수 A1, A2... An 에 게 두 개의 수 를 골 라 서 이 를 하거나 얻 은 결과 가 가장 큰 것 은 얼마 입 니까?N <= 1e5, 0 <= Ai < 2^31
해답: 저 는 처음에 모든 숫자 를 2 진법 으로 표시 한 다음 에 사전 나 무 를 만 들 수 있 었 습 니 다.그리고 공공 부분의 긍정 적 인 차이 나 값 은 1 이다.
그리고 가장 깊 은 결점 의 수 를 첫 번 째 숫자 로.................................................................
문 제 를 보고 거꾸로 저장 해 야 한 다 는 것 을 알 게 되 었 습 니 다. 즉, 31 위 에서 30 위 까지...........................................................................순서대로 저금 하 는 것 은 매우 번거롭다.
마지막 으로 각 계산 한 결 과 를 max 로 취하 면 됩 니 다.
#include
#include
#include
#include
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 4e6;
int tire[MAXN][2], tot = 1;
void read(int& x)
{
int f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
void add(int x)
{
int p = 1;
for(int i = 30; i >= 0; i--)
{
int now = (x >> i) & 1;
if(!tire[p][now]) tire[p][now] = ++tot;
p = tire[p][now];
}
}
int search(int x)
{
int p = 1, res = 0;
for(int i = 30; i >= 0; i--)
{
int now = (x >> i) & 1;
if(tire[p][now ^ 1])
{
p = tire[p][now ^ 1];
res |= (1 << i);
}
else p = tire[p][now]; //
}
return res;
}
int main()
{
int n; read(n);
int ans = 0;
REP(i, 0, n)
{
int x; read(x);
add(x);
ans = max(ans, search(x));
}
printf("%d
", ans);
return 0;
}
poj 3764
처음에는 길 을 구 하 는 것 이 번 거 로 워 서 어떻게 해 야 할 지 몰 랐 다.
문 제 를 풀 어 보 니 lca 의 사상 으로 할 수 있 었 다. lca 의 이전 부분 이 다 르 거나 일어나 면 0 이 었 기 때문에 x 에서 뿌리 까지 의 값 ^ y 에서 뿌리 까지 의 값 = x 에서 y 의 값
그러면 우 리 는 각 노드 에서 뿌리 까지 의 값 을 미리 처리 할 수 있다. 그러면 다음 문제 로 바 뀔 것 이다.
그리고 이 문 제 는 미 친 카드!!나 는 vector 로 테 두 리 를 저장 한 후에 끊 겼 다.
그래서 나 는 어 쩔 수 없 이 인접 시 계 를 배 웠 다.그리고 심심 해서 독 우의 효 과 를 보고, 독 우 를 빼 고 바로 0.94S 로 치 솟 았 다.
우 대 박!
그리고 디 테 일 을 조심 하 시 면 됩 니 다.
#include
#include
#include
#include
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXM = 4e6;
int tire[MAXM][2], n, tot, num;
int d[MAXN], head[MAXN];
struct edge { int to, w, next; };
edge e[MAXN << 1]; // 2
void addedge(int from, int to, int w)
{
e[tot] = edge{to, w, head[from]};
head[from] = tot++;
}
void read(int& x)
{
int f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
void dfs(int u, int fa)
{
for(int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to, w = e[i].w;
if(v == fa) continue;
d[v] = d[u] ^ w;
dfs(v, u);
}
}
void add(int x)
{
int p = 1;
for(int i = 30; i >= 0; i--)
{
int now = (x >> i) & 1;
if(!tire[p][now]) tire[p][now] = ++num;
p = tire[p][now];
}
}
int search(int x)
{
int p = 1, res = 0;
for(int i = 30; i >= 0; i--) //0 2^31-1 30 0
{
int now = (x >> i) & 1;
if(tire[p][now ^ 1])
{
p = tire[p][now ^ 1];
res |= (1 << i);
}
else p = tire[p][now];
}
return res;
}
int main()
{
while(~scanf("%d", &n))
{
memset(tire, 0, sizeof(tire));
memset(head, -1, sizeof(head));
num = 1; tot = 0; // ,
REP(i, 1, n)
{
int u, v, w;
read(u); read(v); read(w);
addedge(u, v, w);
addedge(v, u, w);
}
dfs(0, -1);
int ans = 0;
REP(i, 0, n)
{
ans = max(ans, search(d[i]));
add(d[i]);
}
printf("%d
", ans);
}
return 0;
}
poj 3630
이 벌 거 벗 은 문제 로 마무리 하도록 하 겠 습 니 다.
문자열 을 입력 하여 다른 접두사 가 있 는 지 확인 하 십시오.
두 가지 경우 가 있어 요.
(1) 가입 할 때 새로운 노드 를 만 들 지 않 았 다 면 이 문자열 은 다른 문자열 의 접두사 입 니 다.
(2) 가입 할 때 문자 종점 을 만나면 현재 문자열 의 접두사 가 있 습 니 다.
#include
#include
#include
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 1e4 + 10;
int tire[MAXN * 10][15], end[MAXN * 10], tot = 1;
bool add(char* s)
{
int p = 1;
bool ok = false;
REP(i, 0, strlen(s))
{
if(end[p]) return false;
int ch = s[i] - '0';
if(!tire[p][ch]) tire[p][ch] = ++tot, ok = true;
p = tire[p][ch];
}
end[p] = 1;
return ok;
}
int main()
{
int T, n;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
bool ans = true;
tot = 1;
memset(tire, 0, sizeof(tire));
memset(end, 0, sizeof(end));
REP(i, 0, n)
{
char s[15];
scanf("%s", s);
if(!add(s)) ans = false;
}
printf("%s
", ans ? "YES" : "NO");
}
return 0;
}
다음으로 전송:https://www.cnblogs.com/sugewud/p/9819315.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.