타이어 트 리 요약 (템 플 릿 + 예제)

원본 링크:http://www.cnblogs.com/sugewud/p/9819315.html
제목 은 에서 나 왔 다.
 
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

좋은 웹페이지 즐겨찾기