1 Star 0 Fork 0

南陽劉子驥 / OI Codes

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
p3808.cpp 1.19 KB
一键复制 编辑 原始数据 按行查看 历史
南陽劉子驥 提交于 2022-06-15 14:11 . 20220615
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000010;
struct trie
{
int s[26];
int cnt;
int fail;
}tr[N];
int idx = 0;
void insert(string s)
{
int u = 0;
for(int i = 0; i < s.length(); i++)
{
if(tr[u].s[s[i] - 'a'] != 0)u = tr[u].s[s[i] - 'a'];
else
{
tr[u].s[s[i] - 'a'] = ++idx;
u = idx;
}
}
tr[u].cnt++;
}
void get_fail()
{
queue<int>q;
for(int i = 0; i < 26; i++)
if(tr[0].s[i])q.push(tr[0].s[i]);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0; i < 26; i++)
{
if(tr[u].s[i])
{
tr[tr[u].s[i]].fail = tr[tr[u].fail].s[i];
q.push(tr[u].s[i]);
}
else
{
tr[u].s[i] = tr[tr[u].fail].s[i];
}
}
}
}
int query(string s)
{
int u = 0;
int res = 0;
for(int i = 0; i < s.length(); i++)
{
u = tr[u].s[s[i] - 'a'];
for(int j = u; j > 0 && tr[j].cnt > 0; j = tr[j].fail)
{
res += tr[j].cnt;
tr[j].cnt = 0;
}
}
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
insert(s);
}
get_fail();
string t;
cin >> t;
cout << query(t) << endl;
return 0;
}
1
https://gitee.com/kaiserwilheim/OIcodes.git
git@gitee.com:kaiserwilheim/OIcodes.git
kaiserwilheim
OIcodes
OI Codes
master

搜索帮助