天天看點
傳回

樂師理工acm集訓-字典樹HihoCoder1014 Trie樹【字典樹】POJ2001 Shortest Prefixes【字典樹】HDU2072 單詞數【字典樹/set + 輸入處理】HDU1247 Hat’s Words【字典樹/set + 單詞拆分】

文章目錄

  • HihoCoder1014 Trie樹【字典樹】
    • 解題思路
    • AC代碼
  • POJ2001 Shortest Prefixes【字典樹】
    • 題目大意
    • 解題思路
    • AC代碼
  • HDU2072 單詞數【字典樹/set + 輸入處理】
    • 說明
    • 解題思路
    • AC代碼1【字典樹 + 普通處理】
    • AC代碼2【set + stringstream流】
    • AC代碼3【set + strtok】
  • HDU1247 Hat’s Words【字典樹/set + 單詞拆分】
    • 題目大意
    • 解題思路
    • AC代碼1【字典樹 + 拆分】
    • AC代碼2【set + 拆分】

HihoCoder1014 Trie樹【字典樹】

傳送門：HihoCoder1014 Trie樹

解題思路

  建立字典樹，過程中記錄每個字母結點走過的次數。

  注意：結點數組要開 單詞個數*單詞長度 大小。因為最壞的情況是每次插入的單詞都和已有的單詞沒有公共字首。

AC代碼 

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int tree[MAXN][26];
int vis[MAXN],node = 1;
char s[MAXN];
void insert(char s[])
{
	int len = strlen(s);
	int p = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tree[p][ch]) // 沒有結點
		{
			tree[p][ch] = node++; // 配置設定一個結點
		}
		p = tree[p][ch];
		vis[p]++; // 統計結點通路次數
	}
	return ;
}
int search(char s[])
{
	int len = strlen(s);
	int p = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if(!tree[p][ch]) // 沒有對應結點
		{
			return 0;
		}
		p = tree[p][ch];
	}
	return vis[p]; 
}
int main()
{
	int n;
	scanf("%d",&n);
	while (n--)
	{
		scanf("%s",&s);
		insert(s);
	}
	scanf("%d",&n);
	while (n--)
	{
		scanf("%s",&s);
		printf("%d\n",search(s));
	}
}

POJ2001 Shortest Prefixes【字典樹】

傳送門：POJ2001 Shortest Prefixes

題目大意

  給定一組單詞，找出對于每個單詞能唯一(無歧義)辨別該單詞的最短字首。

解題思路

  根據給定的一組單詞建立字典樹，對于每個單詞找到第一個不是公共字首的字母即可。

AC代碼 

#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN = 2e4+5;
int tree[MAXN][26];
int vis[MAXN],node = 1;
char s[MAXN][21];
void insert(char s[])
{
	int len = strlen(s);
	int p = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tree[p][ch])
		{
			tree[p][ch] = node++;
		}
		p = tree[p][ch];
		vis[p]++;
	}
	return ;
}
void search(char s[])
{
	int len = strlen(s);
	int p = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		p = tree[p][ch];
		putchar(s[i]); // 輸出字母，直到不在公共字首裡
		// 隻通路了一次，說明該字母不在公共字首裡
		// 則 公共字首 + 該字母 能唯一辨別該單詞
		if (vis[p] == 1)
		{
			return ;
		}
	}
}
int main()
{
	int ind = 0;
	while (~scanf("%s",&s[ind]))
	{
		insert(s[ind]);
		ind++;
	}
	for (int i = 0; i < ind; i++)
	{
		printf("%s ",s[i]);
		search(s[i]);
		printf("\n");
	}
}

HDU2072 單詞數【字典樹/set + 輸入處理】

傳送門：HDU2072 單詞數

說明

  這道題主要麻煩在輸入是一行，要對其進行單詞的提取，而且可能會存在單詞間間隔多個空格或末尾是空格的情況。

解題思路

  對于一行中的每個單詞，判斷是否出現過，如果沒出現過，将其加入已出現集合并把個數加一，如果出現過則不作處理。

  對于判斷是否出現過和加入已出現集合可以采用字典樹或者set。

AC代碼1【字典樹 + 普通處理】 

#include<bits/stdc++.h>
using namespace std;
const int MAXN =  5e4 + 5;
int tree[MAXN][30];
int vis[MAXN*100],node = 1;
void insert(string s)
{
	int len = s.size();
	int p = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tree[p][ch])
		{
			tree[p][ch] = node++;
		}
		p = tree[p][ch];
	}
	vis[p] = 1; // 标記結尾	
}
bool search(string s)
{
	int len = s.size();
	int p = 0,cnt = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tree[p][ch])
		{
			return 0;
		}
		p = tree[p][ch];
	}
	return vis[p];
}
int main()
{
	string s,temp;
	while (getline(cin,s) && s[0] != '#')
	{
		int len = s.size(), ans = 0;
		temp = "";
		// 提取出一行中的每個單詞
		for (int i = 0; i < len; i++)
		{
			if(s[i] == ' ')
			{
				// 單詞不為空且字典樹中沒有
				if (temp != "" && !search(temp))
				{
					ans++;
					insert(temp);
					temp = ""; // 重置
				}
			}
			else
			{
				temp += s[i]; // 複制單詞
			}
		}
		// 别忘了處理最後一個
		if (temp != "" && !search(temp))
		{
			ans++;
		}
		cout << ans << "\n";
		memset(tree,0,sizeof(tree));
		memset(vis,0,sizeof(vis));
		node = 1;
	}
	return 0;
}

AC代碼2【set + stringstream流】 

#include<bits/stdc++.h>
using namespace std;
const int MAXN =  5e4 + 5;
set<string> st;
int main()
{
	string s,temp;
	while (getline(cin,s) && s[0] != '#')
	{
		stringstream str(s);
		while (str >> temp)
		{
			st.insert(temp);
		}
		cout << st.size() << "\n";
		st.clear();
	}
	return 0;
}

AC代碼3【set + strtok】 

#include<bits/stdc++.h>
using namespace std;
const int MAXN =  5e4 + 5;
set<string> st;
char s[MAXN], *p;
int main()
{
	while (gets(s) && s[0] != '#')
	{
		p = strtok(s, " ");
		while (p)
		{
			st.insert(p);
			p = strtok(NULL," ");
		}
		cout << st.size() << "\n";
		st.clear();
	}
	return 0;
}

HDU1247 Hat’s Words【字典樹/set + 單詞拆分】

傳送門：HDU1247 Hat’s Words

題目大意

  給定一組單詞，若某個單詞能由其他兩個單詞拼接而成，就輸出它。

  注意：同一個單詞用兩次，以此拼接成另一個單詞也是可以的。

輸入
a
aa
輸出：
aa
解釋：
a + a = aa

解題思路

  先将所有單詞存儲起來，然後對每個單詞進行拆分，判斷被拆分的兩部分是否是單獨的單詞。

AC代碼1【字典樹 + 拆分】 

#include<bits/stdc++.h>
using namespace std;
const int MAXN =  5e4 + 5;
int tree[MAXN][30];
int vis[MAXN*100],node = 1;
char s[MAXN][100],s1[100],s2[100];;
void insert(char s[])
{
	int len = strlen(s);
	int p = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tree[p][ch])
		{
			tree[p][ch] = node++;
		}
		p = tree[p][ch];
	}
	vis[p] = 1; // 标記單詞結尾	
}
bool search(char s[])
{
	int len = strlen(s);
	int p = 0,cnt = 0;
	for (int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tree[p][ch])
		{
			return 0;
		}
		p = tree[p][ch];
	}
	return vis[p];
}
int main()
{
	int ind = 0;
	while (~scanf("%s",&s[ind]))
	{
		insert(s[ind]);
		ind++;
	}
	for (int i = 0; i < ind; i++)
	{
		int len = strlen(s[i]);
		for (int j = 1; j < len; j++)
		{
			// 複制全部
			strcpy(s1,s[i]);
			// 再從 j 位置截斷
			s1[j] = '\0'; 
			// 複制後一部分
			strcpy(s2,s[i] + j);
			// 如果兩部分都是單獨的單詞
			if (search(s1) && search(s2))
			{
				printf("%s\n",s[i]);
				// 該單詞判斷結束
				break;
			}
		}
	}
	return 0;
}

AC代碼2【set + 拆分】 

#include<bits/stdc++.h>
using namespace std;
const int MAXN =  5e4 + 5;
set<string> st;
int main()
{
	string s, a, b;
	while (cin >> s)
	{
		st.insert(s);
	}
	for (auto it : st)
	{
		int size = it.size();
		for (int i = 1; i < size; i++)
		{
			a = it.substr(0, i);
			b = it.substr(i, size - i);
			if (st.count(a) && st.count(b))
			{
				cout << it << "\n";
				break;
			}
		}
	}
	return 0;
}
2020暑假集訓
上一篇: Clucene索引合并剖析
下一篇: View位置資訊

繼續閱讀