传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3695
题意:给你n个字串和一个母串,问你有多少个字串与母串匹配(如果某一字串不匹配,那么看它的反转字符串匹不匹配)。
题解:第一道自己做的没看别人题解的AC自动机,而且还是1A,好激动的说,开始向普通AC自动机一样扫一遍,然后记录那些已经被匹配,然后加入未被匹配的反转字符串,再扫一遍,两个的和即位答案。
AC代码:
Accepted |
3695 |
1312MS |
30488K |
4964 B |
G++ |
XH_Reventon |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=33;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
#define N 500010
#define L 27 //表示字符串范围
char str[5500010], keyword[1111],ss[5500010];
int head, tail;
char xh[255][1111];
bool vis[255];
struct node
{
node *fail;
node *next[L];
int count;
int di;
node() //init内联
{
fail = NULL;
count = 0;
di=-1;
for(int i = 0; i < L; ++i)
next[i] = NULL;
}
}*q[N];
node *root;
void insert(char *str,int ppp) //建立Trie树
{
int temp, len;
node *p = root;
len = strlen(str);
for(int i = 0; i < len; ++i)
{
temp = str[i] - 'A'; //由题意决定
if(p->next[temp] == NULL)
p->next[temp] = new node();
p = p->next[temp];
}
p->count++;
p->di=ppp;
}
void build_ac() //初始化fail指针,BFS
{
head= tail = 0;
q[tail++] = root;
while(head != tail)
{
node *p = q[head++]; //弹出队头
node *temp = NULL;
for(int i = 0; i < L; ++i)
{
if(p->next[i] != NULL)
{
if(p == root) //第一个元素fail必指向根
p->next[i]->fail = root;
else
{
temp = p->fail; //失败指针
while(temp != NULL) //2种情况结束:匹配为空or
{
if(temp->next[i] != NULL) //找到匹配
{
p->next[i]->fail = temp->next[i];
break;
}
temp = temp->fail;
}
if(temp == NULL) //为空则从头匹配
p->next[i]->fail = root;
}
q[tail++] = p->next[i]; //入队
}
}
}
}
int query() //扫描
{
int index, len, result;
node *p = root; //Tire入口
result = 0;
len = strlen(str);
for(int i = 0; i < len; ++i)
{
index = str[i] - 'A'; //由题意决定
while(p->next[index] == NULL && p != root) //跳转失败指针
p = p->fail;
p = p->next[index];
if(p == NULL)
p = root;
node *temp = p; //p不动,temp计算后缀串
while(temp != root && temp->count != -1)
{
result += temp->count;
vis[temp->di]=1;
temp->count = -1;
temp = temp->fail;
}
}
return result;
}
void deal(node *T)
{//若果有多组数据-多棵树,那么要释放内纯
int i;
if(T==NULL)
return ;
for(i=0;i<L;i++)
if(T->next[i]!=NULL)
deal(T->next[i]);
free(T);//释放
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof(vis));
root = new node();
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",keyword);
insert(keyword,i);
int len=strlen(keyword);
for(int j=0;j<len;j++)
xh[i][j]=keyword[len-j-1];
xh[i][len]='\0';
}
build_ac();
scanf("%s",ss);
int len=strlen(ss),p=0;
for(int i=0;i<len;i++)
{
if(ss[i]=='[')
{
int to=0;
i++;
while(ss[i]>='0'&&ss[i]<='9')
{
to=to*10+ss[i]-'0';
i++;
}
char c=ss[i];
for(int j=0;j<to;j++) str[p++]=c;
i++;
}
else
str[p++]=ss[i];
}
str[p]='\0';
int sum=query();
deal(root);
root = new node();
for(int i=0;i<n;i++)
{
if(vis[i]==1) continue;
insert(xh[i],i);
}
build_ac();
sum+=query();
deal(root);
cout<<sum<<endl;
}
return 0;
}
//Accepted 3695 1312MS 30488K 4964 B G++ XH_Reventon
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码