个人网站源代码,宜昌网站建设制作公司,qq网页版登录官网登录入口,wordpress常用插件模板
模板总共分为两部分
插入一个字符串查找一个字符串
int idx 0;
int trie[3000010][150];
int ans[3000010];##原理
trie[上节点编号][下方连接的字母] 下方连接的字母的节点编号
trie[0][0]1;trie[0][1]5; trie[1][1]2; trie[2][1]4;trie[2][2]3; trie[5][2]6; tri…模板
模板总共分为两部分
插入一个字符串查找一个字符串
int idx 0;
int trie[3000010][150];
int ans[3000010];##原理
trie[上节点编号][下方连接的字母] 下方连接的字母的节点编号
trie[0][0]1;trie[0][1]5; trie[1][1]2; trie[2][1]4;trie[2][2]3; trie[5][2]6; trie[6][0]7; 其余trie[i][j]都为0即空节点 cnt[4]cnt[3]cnt[6]cnt[7]1; void insert(string s)
{int p 0;for (int i 0; i s.size(); i){int x s[i] - a;if (trie[p][x] 0) trie[p][x] id;p trie[p][x];//cnt[p] //如果是寻找前缀和相同 在这里cnt[p]}cnt[p];//如果是寻找完全相同 在这里cnt[p]
}int find(string s)
{int p 0;for (int i 0; i s.size(); i){int x s[i] - a;if (trie[p][x] 0)return 0;p trie[p][x];}return cnt[p];
}例题 步骤
#includeiostream
#define endl \n
using namespace std;
int idx 0;
int trie[3000010][150];
int ans[3000010];
int trans(char s)
{if (s a s z){return s - a 26;}if (s A s Z){return s - A;}if (s 0 s 9){return s - 0 52;}}
void insert1(string s)
{int p 0;for (int i 0; s[i]; i){int x trans(s[i]);if (!trie[p][x]) trie[p][x] idx;p trie[p][x];ans[p];}
}
int find1(string k)
{int p 0;for (int i 0; k[i]; i){int x trans(k[i]);if (!trie[p][x]) return 0;p trie[p][x];}return ans[p];
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int num;cin num;for (int i 1; i num; i){for (int x 0; x idx; x){for (int y 0; y 122; y){trie[x][y] 0;}}for (int l 0; l idx; l){ans[l] 0;}idx 0;int n, m;cin n m;for (int j 1; j n; j){string s;cin s;insert1(s);}for (int k 1; k m; k){string s;cin s;coutfind1(s)endl;}}return 0;
}
